递归和循环在内存使用方面令人困惑的差异

Question

我用 c 和 python 编写了一个非常简单的选择排序代码（以确认原因）

想法很简单，就是找到运行时和内存使用情况的差异，以找到在这种情况下更好的方法递归或循环。

令人惊讶的是，C 和 Python 中递归的内存消耗都比循环的使用量要少。

这是我使用的 c 和 python 代码。

C

循环法

#include <stdio.h>

void select_sort(int *_a){
    for(int i = 0; i < 10; i ++){
        for(int j = i; j < 10; j++){
            if(*(_a + j) < *(_a + i)){
                int temp = *(_a + i);
                *(_a + i) = *(_a + j);
                *(_a + j) = temp;
            }
        }
    }
}


int main() {
    
    int a[10] = {9,8,4,33,45,65,67,87,23,45};
    select_sort(&a);
    
    for(int i = 0; i < 10; i++)printf("%d ",*(a + i));
    return 0;
}

递归法

#include <stdio.h>

void select_sort(int *_a){
    sort(_a,0);
}

void sort(int *_a, int k){
    if(k < 9){
        for(int i = k + 1; i < 10; i++){
            if(*(_a) > *(_a + i)){
                int temp = *(_a);
                *(_a) = *(_a + i);
                *(_a + i) = temp;
            }
            sort(_a,k+1);
        }    
    }
}

int main() {
    
    int a[10] = {9,8,4,33,45,65,67,87,23,45};
    select_sort(&a);
    
    for(int i = 0; i < 10; i++)printf("%d ",*(a + i));
    return 0;
}

Python 循环法

def select_sort(arr):
  
  for i in range(0,len(arr)):
    small = i
    for j in range(i,len(arr)):
      if arr[j] < arr[small]:
        small = j
    arr[i],arr[small] = arr[small],arr[i]
  return arr

arr = [1,3,5,8,56,764,6,75,468,4,5]
print(select_sort(arr))

递归法

def select_sort(arr):
  sort(arr,0)

def sort(arr,k):
  if k < len(arr)-1:
    small = k
    for j in range(k,len(arr)):
      if arr[j] < arr[small]:
        small = j
    arr[k],arr[small] = arr[small],arr[k]
    sort(arr,k+1)

arr = [1,3,5,8,56,764,6,75,468,4,5]
select_sort(arr)
print(arr)

我的问题是为什么 递归应该使用更多内存，因为它向堆栈添加了额外的内存层。

Answer 1

两个版本的堆栈都是相同的。在运行时使用了多少是另一回事。对于像您这样的小程序，很难测量运行时的最大内存消耗。