C语言递归
递归是当函数调用自身的副本以解决较小的问题时出现的过程。调用自身的任何函数都称为递归函数，此类函数调用称为递归调用。递归涉及多个递归调用。但是，强加递归的终止条件很重要。递归代码比迭代代码短，但是很难理解。
递归不能应用于所有问题，但是对于可以根据类似子任务定义的任务更为有用。例如，递归可应用于排序，搜索和遍历问题。
通常，由于函数调用始终是开销，因此迭代解决方案比递归更有效。任何可以递归解决的问题，也可以迭代解决。但是，某些问题最适合通过递归解决，例如，河内塔，斐波那契数列，阶乘发现等。
在以下示例中，使用递归来计算a的阶乘数字。
#include <stdio.h>
int fact (int);
int main()
{
int n,f;
printf("Enter the number whose factorial you want to calculate?");
scanf("%d",&n);
f = fact(n);
printf("factorial = %d",f);
}
int fact(int n)
{
if (n==0)
{
return 0;
}
else if ( n == 1)
{
return 1;
}
else
{
return n*fact(n-1);
}
}
输出
Enter the number whose factorial you want to calculate?5
factorial = 120
通过下图可以了解递归方法调用的上述程序:
递归函数
递归函数通过将其划分为子任务来执行任务。在函数中定义了一个终止条件，该终止条件由某些特定的子任务满足。此后，递归停止，并且从函数返回最终结果。
函数不递归的情况称为基本情况，而函数不断调用自身以执行以下操作的实例子任务，称为递归案例。所有递归函数都可以使用这种格式编写。
下面提供了用于编写任何递归函数的伪代码。
if (test_for_base)
{
return some_value;
}
else if (test_for_another_base)
{
return some_another_value;
}
else
{
// Statements;
recursive call;
}
C语言中的递归示例
让我们看一个示例来查找斐波那契数列的第n个项。
#include<stdio.h>
int fibonacci(int);
void main ()
{
int n,f;
printf("Enter the value of n?");
scanf("%d",&n);
f = fibonacci(n);
printf("%d",f);
}
int fibonacci (int n)
{
if (n==0)
{
return 0;
}
else if (n == 1)
{
return 1;
}
else
{
return fibonacci(n-1)+fibonacci(n-2);
}
}
输出
Enter the value of n?12
144
递归方法的内存分配
每个递归调用都会在内存中创建该方法的新副本。该方法返回一些数据后，副本将从内存中删除。由于在函数内部声明的所有变量和其他内容都存储在堆栈中，因此在每次递归调用时都维护一个单独的堆栈。从相应的函数返回该值后，堆栈将被破坏。递归在解析和跟踪每个递归调用中的值时涉及非常多的复杂性。因此，我们需要维护堆栈并跟踪堆栈中定义的变量的值。
让我们考虑以下示例，以了解递归函数的内存分配。
int display (int n)
{
if(n == 0)
return 0; // terminating condition
else
{
printf("%d",n);
return display(n-1); // recursive call
}
}
解释
让我们检查一下n = 4的递归函数。首先，所有堆栈都被维护，打印出相应的n值，直到n变为0，达到终止条件后，通过将0返回到其调用堆栈，堆栈将一一销毁。请考虑以下图像，以获取有关递归函数的堆栈跟踪的更多信息。
