定义：
递归是一种函数直接或间接调用自身的技术。
直接表示它将自行调用。间接意味着，它将调用将递归调用自身的函数。
让我们借助示例来了解递归：
下面是查找递归函数调用次数的程序。
#include<iostream>
using namespace std;
int fun(int n)
{
if (n == 1)
return 1; // base case
else
return 1 + fun(n-1);
}
int main()
{
int n = 5;
cout<< "The number of times the function are "<<fun(5)<<endl;
return 0;
}
在上面的程序中，函数“ fun（）”是递归函数。 “ main（）”正在间接调用递归函数。然后，函数“ fun（）”将直接调用自身。
为了编写任何递归函数，应该有一个基本情况。基本情况用于退出递归循环。如果不存在基本情况，则将导致堆栈溢出并使程序崩溃。
因此，对于每个递归程序，都应该有一个基本案例。
递归和堆栈框架：
通过以上程序，我们将了解使用递归函数时如何影响堆栈帧。
因此，我们调用了n = 3值的函数。我们知道，在C中，局部c变量存储在堆栈中。调用函数时，该函数的激活记录以及功能参数也会一起存储。
因此，从main（）函数中，我们调用fun（）函数。
堆栈框架：
fun（）函数中的更改：
int fun(3 )
{
if (n == 1)
return 1; // base case
else
return 1 + fun(2);
}
当我们调用fun（2）时，我们将控件从fun（3）转移到fun（2），如上所示。
现在进行中（2）
堆栈框架：
fun（）函数中的更改：
int fun( 2 )
{
if (n == 1)
return 1; // base case
else
return 1 + fun(1);
}
现在我们将乐趣（1）从乐趣（2）中调用。因此，我们将控件从乐趣（2）转移到乐趣（1）。
堆栈框架：
fun（）函数的变化。
int fun( 1 )
{
if (n == 1)
return 1; // base case
}
现在有趣的是（1）现在“ n == 1”为真，因此我们返回1。这意味着，我们正在从堆栈帧返回1到调用函数。我们可以看到调用函数很有趣（2）。
int fun( 2 )
{
else
return 1 + fun(1);
}
int fun( 2 )
{
else
return 1 + 1; // return 2
}
因此，2将返回到fun（2）的调用函数。
从堆栈框架中，我们可以看到fun（3）正在调用fun（2）。因此，乐趣（3）将变为：
int fun( 3 )
{
else
return 1 + fun( 2 );
}
int fun( 3 )
{
else
return 1 + 2; // return 3
}
现在，值“ 3”将返回到其调用函数，即main函数。
概括地说，我们可以总结以下步骤：
递归树：
什么是递归树？
如上一节所述，我们了解了什么是递归以及进行递归调用时堆栈框架的变化。
递归树只不过是递归调用的可视化表示。
让我们以打印第n个斐波那契数为例来了解递归树。
查找第n个斐波那契数的伪代码如下：
fib( n )
{
int n <= 1
return n;
else
return fib ( n -1 ) + fib ( n - 2 )
}
当我们用n = 5调用fib函数时。堆栈成帧器和斐波那契树如下所示：
然后fib（5）是一个递归调用，它将是：
现在，编译器正在执行fib（4），其他所有程序都处于暂停状态。
然后fib（4）将调用fib（3），fib（3）将调用fib（2），fib（2）将调用fib（1）…可以如下所示
现在fib（1），它将返回1并从堆栈中弹出。
现在fib（2）在堆栈中，它将调用fib（0）并将fib（0）放入堆栈。
现在fib（0）将返回0，并且由于fib（2）调用了fib（0）和fib（1），fib（2）的最终值将为1，并且fib（2）将弹出堆栈。现在执行将流向fib（3）。
现在，fib（3）已经称为fib（2），因此它将称为fib（1），并且fib（1）将被放入堆栈中。
同样，fib（1）将调用fib（0），它可以显示如下：
现在对于fib（4），它已经称为fib（3），因此它将称为fib（2），再次fib（2）将称为fib（0）和fib（1）。
计算值可以如下：
因此，fib（4）的值为“ 2 +1 = 3”。 3将返回fib（5）
再次，fib（5）将调用fib（3），fib（3）将调用fib（2），然后fib（2）将调用fib（1）。 Fib（1）将返回0。
最终的递归树将如下所示：
这是递归的基础，也是调用递归函数时堆栈帧中的更改。
这是一个重要的话题。因为在下一章，即动态编程和回溯中，它使用递归来获取结果。
进一步阅读：
AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。
该网站上可用的教程列表：
| C编程20+章 | C ++编程80+章 |
| 100多个编码问题 | 数据结构和算法85+章 |
| 系统设计20+章 | Shell脚本编写12章 |
| 4g LTE 60+章节 | 最常见的编码问题 |
| 5G NR 50+章 | Linux系统编程20+章 |
