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 的二元搜索算法，而不使用递归函数调用。在这种情况下，采用循环的解决方案通常会比采用递归的解决方案执行效率更高。