为什么这个递归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

你在这里比较苹果和橘子.您的第一个算法是迭代冒泡排序,第二个算法是递归选择排序.(它被标记为冒泡排序,但事实并非如此.请注意,它通过查找最小值并将其交换到数组的前面来工作.)因为您正在查看两种完全不同的算法,所以绘制它并不一定有意义关于递归与迭代的任何结论.

我认为值得指出你正在使用的选择排序的特定递归实现是尾递归(只有一个递归调用,它位于函数的最后.)许多编译器足够聪明以优化尾递归因此根本不涉及递归,代码转换为使用循环.换句话说,您可能甚至没有看到设置和拆除堆栈帧的成本.

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

希望这可以帮助!