如何通俗易懂地理解递归_递归通俗易懂

一、引例

描述

给定一个数字 n(范围在0~10)，求 n 的阶乘

样例

输入：0 
输出：1
1
2

输入：5
输出：120
1
2

算法设计

首先最容易想到的就是利用循环做，即进行 n-1 次循环，然后每次循环中进行累乘，最后输出结果，再加一个特殊值判断(0! = 1)，那么很容易编写代码如下：

#include <iostream>

int main()
{
    int n = 0,num = 1;
    std::cin >> n;
    while(n > 0)
        num *= n--;
    std::cout << num;
}
1
2
3
4
5
6
7
8
9
10

接下来看看递归的版本

二、原理

1.定义(引自维基百科)

递归（英语：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。

2.观察题目特征

在求阶乘的过程中，while循环中的语句不断的执行，这就跟递归定义中自我复制的概念很像，即不断地进行乘法运算，将其定义为规律1，每次乘的数字不一样，如果可以找到数字变化的规律，将其称为规律2，那么我们就可以将规律1和规律2组合起来，描述求阶乘这一问题。
显然，此题中规律1和规律2都是确定的，分别是进行乘法运算和变量值减一。那么什么时候这一过程会终止？显然是由规律2决定的，当变量减到 0 的时候就会停止。那么现在就有了一个完整的表述：有一个函数描绘了这一过程，函数自己调用自己实现累乘，每次需要函数传入变量的值，当变量的值为 0 时，函数停止调用自己。

3.代码表述

#include <iostream>

int Factorial(int n) {
    if (n == 0)
        return 1;
    return n * Factorial(n - 1);
}

int main()
{
    int n = 0;
    std::cin >> n;
    std::cout << Factorial(n);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

三、如何写递归