c - 为什么递归 C 代码比迭代代码快？

Question

我一直被教导说递归方法比迭代方法慢，因为递归需要分配一个新的堆栈帧。我记得这是这两者的明显区别之一。

但是，在下面的 C 程序中，我看到递归函数比迭代函数更快。!!!

/****Bubble Sort (by iteration)****/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

/****Bubble Sort Function declaration****/
void sort(int *,int);

/****Main Function****/
int main()
   {
    int n,*arr,i;
    float exetime;
    clock_t cstart,cend=0;

    printf("Enter the number of elements: ");
    scanf("%d",&n);

    arr=malloc(n*sizeof(int));

    printf("Enter the array elements: ");
    for(i=0;i<n;i++)
        scanf("%d",&arr[i]);

    cstart=clock(); //starting time
    for(i=0;i<10000;i++)
    sort(arr,n);
    cend=clock();   //end time

    exetime=(float)(cend-cstart)/CLOCKS_PER_SEC;
    printf ("%.4f \xC2\xB5sec\n",exetime*100);

    for(i=0;i<n;i++)
    printf("%-2d",arr[i]);

    free(arr);
    return 0;
   }

/****Bubble Sort Function****/
void sort(int *arr,int n)
    {
     int i,j,temp;

      for(i=0;i<=n-2;i++)

        for(j=0;j<=n-2-i;j++)               

            if(arr[j+1]<arr[j])      
              {                    
               temp=arr[j+1];
               arr[j+1]=arr[j];
               arr[j]=temp;
              } 
    }                                                                          

输出:

输入元素个数:5

输入数组元素:5 4 3 2 1

0.1262 微秒

1 2 3 4 5

/****Bubble Sort (by recursion)****/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

/****Bubble Sort Function declaration****/
void sort(int *,int);

/****Main Function****/
int main()
   {
    int n,*arr,i;
    float exetime;
    clock_t cstart,cend=0;

    printf("Enter the number of elements: ");
    scanf("%d",&n);

    arr=malloc(n*sizeof(int));

    printf("Enter the array elements: ");
    for(i=0;i<n;i++)
        scanf("%d",&arr[i]);

    cstart=clock(); //starting time
    for(i=0;i<10000;i++)
    sort(arr,n);
    cend=clock();   //end time

    exetime=(float)(cend-cstart)/CLOCKS_PER_SEC;
    printf ("%.4f \xC2\xB5sec\n",exetime*100);

    for(i=0;i<n;i++)
    printf("%-2d",arr[i]);

    free(arr);
    return 0;
   }

/****Bubble Sort Function****/
void sort(int *arr,int n)
   {
    static int i=0;
    int j,temp;

    for(j=0;j<=n-2-i;j++)  

        if(arr[j+1]<arr[j])      
         {                 
           temp=arr[j+1];
           arr[j+1]=arr[j];
           arr[j]=temp;
         }

    if(++i<=n-2) 
       sort(arr,n);
  }

输出:

输入元素个数:5

输入数组元素:5 4 3 2 1

0.0227 微秒

1 2 3 4 5

Answer 1

您在这里将苹果与橙子进行比较。您的第一个算法是迭代冒泡排序，第二个是递归选择排序。 (它被标记为冒泡排序，但实际上不是。请注意，它的工作原理是找到最小值并将其交换到数组的前面。)由于您正在查看两种完全不同的算法，因此绘制不一定有意义关于递归与迭代的任何结论。

我认为还值得指出的是，您正在使用的选择排序的特定递归实现是尾递归(只有一个递归调用，它在函数的最后。 ) 许多编译器足够聪明，可以优化尾递归，从而完全不涉及递归，并将代码转换为使用循环。换句话说，您甚至可能看不到此处设置和拆除堆栈框架的成本。

最后，虽然递归算法通常会因设置和拆除堆栈帧而产生成本，这是正确的，但这并不一定意味着递归算法本质上总是比迭代算法慢。在某些情况下，自然递归的算法的迭代版本通过维护显式堆栈并对其执行操作来工作。根据堆栈的实现，该堆栈可能最终需要在堆中动态分配内存，这通常比设置和拆除堆栈帧更昂贵。与往常一样，如果您有两种算法并想比较它们的经验性能，最好将这两种算法相互比较，看看哪个获胜。

希望这对您有所帮助!