首页 > 编程笔记

C语言递归函数

递归(recursive)函数是“自己调用自己”的函数,无论是采用直接或间接调用方式。间接递归意味着函数调用另一个函数(然后可能又调用第三个函数等),最后又调用第一个函数。因为函数不可以一直不停地调用自己,所以递归函数一定具备结束条件。

在例 1 中,递归函数 binarySearch()实现二元搜索算法,在排序好的数组中找到特定元素。首先,该函数根据搜索条件比较数组最中间的元素。如果相同,就返问该元素的指针,表示找到了;如果不相同,该函数会调用自己,在可能存在满足搜索条件的一半数组中搜索,一直递归地进行下去,指导找到满足搜索条件的元素。如果剩下数组的长度为 0,则表示找不到,那么递归就会结束。

【例1】函数 binarySearch()
// 函数 binarySearch() 在排序好的数组中搜索
// 参数:需要搜索的元素值;待搜索的long类型数组;数组的长度
// 返回值:指向满足搜索条件的元素的指针,或者为NULL,如果数组中没有元素满足搜索条件。
long *binarySearch( long val, long array[ ], int n )
{
  int m = n/2;
  if ( n <= 0 )               return NULL;
  if ( val == array[m] ) return array + m;
  if ( val < array[m] )  return binarySearch( val, array, m );
  else                           return binarySearch( val, array+m+1, n-m-1 );
}

对于有 n 个元素的数组来说,二元搜索算法进行最多 1+log2(n)次比较。如果有一百万个元素,最多比较 20 次,也就是最多 20  次递归执行函数  binarysearch()。

递归函数基于了这样一个事实:每次调用函数时,都会重新建立动态变量。这些变量,以及返回时需要的调用者地址,都存储在栈中,每次函数递归都会造成栈上新增一块数据。程序员要确保栈的空间够大,足以容纳递归的中间处理过程。不过例 1 中的函数 binarySearch()对于栈空间的要求并不大。

递归函数是采用逻辑方式来实现自然递归规律的算法,例如二元搜索技术,或者树状结构导航(navigation)。

然而,即使递归函数可以对某些问题提供优雅而紧凑的解决方案,但采用简单循环的解决方案也常常是可行的。例如,可以用循环改写例 1 的二元搜索算法,而不使用递归函数调用。在这种情况下,采用循环的解决方案通常会比采用递归的解决方案执行效率更高。

推荐阅读