C语言中的递归

上一页
下一页

递归是指一个函数调用自身的过程。C语言允许编写这样的函数，这些函数通过将复杂问题分解成简单易处理的问题来调用自身以解决复杂问题。这些函数被称为递归函数。

什么是C语言中的递归函数？

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

语法

一个通用的递归函数看起来像这样：

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

int main(){
   recursive_function();
}

在使用递归时，程序员需要注意定义函数的退出条件，否则它将进入无限循环。

为什么在C语言中使用递归？

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

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

使用递归计算阶乘

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

递归最流行的例子是阶乘的计算。在数学上，阶乘定义为：

 
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。

示例：非递归阶乘函数

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

#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;
}

输出

运行此代码时，它将产生以下输出：

a: 5 
Factorial of a: 120

示例：递归阶乘函数

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

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

#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;
}

输出

运行代码并检查其输出：

a: 5 
Factorial of a: 120

当main()函数通过传递变量“a”来调用factorial()函数时，它的值将存储在“i”中。factorial()函数连续调用自身。

在每次调用中，"i"的值在减少1后乘以其先前值，直到它达到1。当它达到1时，从参数的初始值到1之间所有值的乘积将返回到main()函数。

使用递归进行二分查找

让我们再看一个例子来了解递归是如何工作的。手头的问题是在数组中检查给定数字是否存在。

虽然我们可以使用for循环并比较每个数字来对列表中的某个数字进行顺序查找，但顺序查找效率不高，尤其是在列表过长的情况下。

二分查找算法检查索引“start”是否大于索引“end”。根据变量“mid”处的值，再次调用该函数以搜索元素。

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

示例：递归二分查找

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

#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

使用递归生成斐波那契数列

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

示例

以下示例使用递归函数为给定数字生成斐波那契数列的前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

在程序中实现递归对于初学者来说比较困难。虽然任何迭代过程都可以转换为递归过程，但并非所有递归案例都可以轻松地迭代表示。

打印页面

上一页
下一页
广告