Cprogramming 简明教程

Recursion in C

Recursion 是一个函数调用自身的过程。C 语言允许编写将自身调用以通过将复杂问题分解为简单易解的问题来解决问题的函数。这些函数被称为 recursive functions 。

What is a Recursive Function in C?

C 中的递归函数是一个 function ，它调用自身。当某个问题以其自身术语定义时，就会使用递归函数。尽管它涉及到迭代，但使用迭代方法来解决此类问题可能会很乏味。递归方法为看似复杂的问题提供了非常简洁的解决方案。

Syntax

一般的递归函数如下所示 −

void recursive_function(){
   recursion();   // function calls itself
}

int main(){
   recursive_function();
}

在使用递归时，程序员需要小心地定义函数的退出条件，否则它将进入 infinite loop 。

Why Recursion is Used in C?

递归用于执行复杂任务，例如 tree 和 graph 结构遍历。常见的递归编程解决方案包括阶乘、二分查找、树遍历、汉诺塔、国际象棋中的八皇后问题等。

递归程序虽然简洁，但不容易理解。即使代码的大小可能减少，但它需要更多的处理器资源，因为它涉及对函数的多个 IO 调用。

Factorial Using Recursion

递归函数对于解决许多数学问题非常有用，例如计算某个数的阶乘、生成斐波那契数列等。

递归最常见的例子是阶乘的计算。在数学上，阶乘的定义如下：

n! = n X (n-1)!

可以看出，我们使用阶乘本身来定义阶乘。因此，这是一个编写递归函数的合适案例。让我们展开上述定义以计算 5 的阶乘值。

5! = 5 X 4!
   5 X 4 X 3!
   5 X 4 X 3 X 2!
   5 X 4 X 3 X  2 X 1!
   5 X 4 X 3 X  2 X 1
   = 120

虽然我们可以使用循环执行此计算，但其递归函数涉及通过递减数字依次调用它，直到数字变为 1。

Example: Non-Recursive Factorial Function

以下程序演示了如何使用非递归函数来计算一个数字的阶乘：

#include <stdio.h>
#include <math.h>

// function declaration
int factorial(int);

int main(){
   int a = 5;
   int f = factorial(a);

   printf("a: %d \n", a);
   printf("Factorial of a: %d", f);
}
int factorial(int x){
   int i;
   int f = 1;

   for (i = 5; i >= 1; i--){
      f *= i;
   }
   return f;
}

Output

当你运行这段代码时，它将产生以下输出：

a: 5
Factorial of a: 120

Example: Recursive Factorial Function

现在让我们编写一个递归函数来计算给定数字的阶乘。

以下示例使用递归函数计算给定数字的阶乘：

#include <stdio.h>
#include <math.h>

/* function declaration */
int factorial(int i){

   if(i <= 1){
      return 1;
   }
   return i * factorial(i - 1);
}
int main(){
   int a = 5;
   int f = factorial(a);

   printf("a: %d \n", a);
   printf("Factorial of a: %d", f);
   return 0;
}

Output

运行代码并检查其输出：

a: 5
Factorial of a: 120

当 main() 函数通过传递变量 "a" 来调用 factorial() 函数时，其值存储在 "i" 中。factorial() 函数依次调用自身。

在每次调用中，“i” 的值都会乘以其较早的值，然后减 1，直到达到 1。当它达到 1 时，参数初始值与 1 之间所有值的乘积将返回给 main() 函数。

Binary Search Using Recursion

让我们看另一个示例来了解递归的工作原理。手头的问题是检查给定的数字是否存在于 ｛@s0｝ 中。

虽然我们可以使用｛@s3｝对列表中的某个数字执行｛@s2｝并比较每个数字，但是顺序搜索效率低下，尤其是当列表过长时。

｛@s4｝ 检查索引 "start" 是否大于索引 "end"。根据变量 "mid" 中存在的值，再次调用该函数以搜索元素。

我们有一个按升序排列的数字列表。然后，我们找到列表的中点，并将检查限制在中点的左侧或右侧，具体取决于所需数字小于还是大于中点的数字。

Example: Recursive Binary Search

以下代码实现了递归二分查找技术 -

#include <stdio.h>

int bSearch(int array[], int start, int end, int element){

   if (end >= start){

      int mid = start + (end - start ) / 2;

      if (array[mid] == element)
         return mid;

      if (array[mid] > element)
         return bSearch(array, start, mid-1, element);
         return bSearch(array, mid+1, end, element);
   }
   return -1;
}

int main(void){
   int array[] = {5, 12, 23, 45, 	49, 67, 71, 77, 82};
   int n = 9;
   int element = 67;
   int index = bSearch(array, 0, n-1, element);

   if(index == -1 ){
      printf("Element not found in the array ");
   }
   else{
      printf("Element found at index: %d", index);
   }
   return 0;
}

运行代码并检查其输出：

Element found at index: 5

Fibonacci Series Using Recursion

在斐波那契数列中，一个数字是其前两个数字的和。要生成斐波那契数列，第 i 个数字是 i-1 和 i-2 的和。

Example

以下示例使用递归函数为给定的数字生成斐波那契数列中的前 10 个数字：

#include <stdio.h>

int fibonacci(int i){

   if(i == 0){
      return 0;
   }

   if(i == 1){
      return 1;
   }
   return fibonacci(i-1) + fibonacci(i-2);
}

int main(){

   int i;

   for (i = 0; i < 10; i++){

      printf("%d\t\n", fibonacci(i));

   }
   return 0;
}

编译并执行上述代码后，将产生以下结果 −

0
1
1
2
3
5
8
13
21
34

初学者难以在程序中实现递归。虽然任何迭代过程都可以转换为一个递归过程，但并非所有递归情况都可以轻松地以迭代方式表示。