C 语言中的递归
递归是指函数调用自身的过程。C 语言允许编写此类函数，通过调用自身将复杂问题分解为简单易行的问题来解决。这些函数被称为递归函数。
什么是 C 语言中的递归函数?
C 语言中的递归函数是指函数调用自身的函数。当某个问题根据自身进行定义时，就会使用递归函数。虽然递归函数涉及迭代，但使用迭代方法解决此类问题可能会非常繁琐。递归方法为看似复杂的问题提供了非常简洁的解决方案。
语法
通用递归函数如下所示 -
void recursive_function(){
recursion(); // 函数调用自身
}
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>
// 函数声明
int factorial(int);
int main(){
int a = 5;
int f = factorial(a);
printf("a: %d
", 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>
/* 函数声明 */
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
", a);
printf("Factorial of a: %d", f);
return 0;
}
输出
运行代码并检查其输出 −
a: 5 Factorial of a: 120
当 main() 函数通过传递变量"a"调用 factorial() 函数时，其值存储在"i"中。factorial() 函数会依次调用自身。
每次调用时，"i"的值都会减 1 后乘以先前的值，直到等于 1。当 i 达到 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
", fibonacci(i));
}
return 0;
}
输出
当编译并执行上述代码时，它会产生以下结果 -
0 1 1 2 3 5 8 13 21 34
在程序中实现递归对于初学者来说比较困难。虽然任何迭代过程都可以转换为递归过程，但并非所有递归情况都能轻松地用迭代方式表达。
