函数的递归调用，C语言函数递归调用完全攻略

前面讲了函数调用，那么函数到底是如何调用的？函数调用是通过栈实现的。在调用函数时，系统会将被调函数所需的程序空间安排在一个栈中。每当调用一个函数时，就在栈顶为它分配一个存储区。每当从一个函数退出时就释放它的存储区。

也就是说，当前正在运行的函数的存储区是在栈顶的。因为栈是先进后出的（或者说是后进先出的），所以当有多个函数嵌套调用时，会按照先调用后返回的原则（或者说是后调用先返回的原则）进行返回。

递归也是一种函数调用，只不过是函数自己调用自己，是一种特殊的函数调用，调用自己同调用别人是一模一样的。

因为递归也是函数调用，所以递归也是用栈实现的。下面来写一个程序，看看函数是如何自己调用自己的：

# include <stdio.h>
void Func(int n);  //函数声明
int main(void)
{
    int n;
    printf("想输出几个我爱你:");
    scanf("%d", &n);
    Func(n);
    return 0;
}
void Func(int n)
{
    if (n > 0)
    {
        printf("i love you\n");
        Func(n-1);
    }
    else
    {
        return ;
    }
}

输出结果是：
想输出几个我爱你:5
i love you
i love you
i love you
i love you
i love you

这就是“自己调用自己”。从这个程序可以看出，自己调用自己必须要满足一个条件，就是必须要知道什么时候结束调用。不然函数就会一直不停地调用，造成“死递归”。

死递归，是指递归的时候没有出口，不知道什么时候停下来，不停地自己调用自己，直到栈满没有地方放了为止。这时计算机也死机了（除了这个条件之外还有另外一个条件，后续再讲）。

使用递归必须要满足的两个条件

并不是所有的问题都能用递归解决。要使用递归就必须要具备两个条件。

递归的思想是：为了解决当前问题 F(n)，就需要解决问题 F(n–1)，而 F(n–1) 的解决依赖于 F(n–2) 的解决……就这样逐层分解，分解成很多相似的小事件，当最小的事件解决完之后，就能解决高层次的事件。这种“逐层分解，逐层合并”的方式就构成了递归的思想。

使用递归最主要的是要找到递归的出口和递归的方式。所以递归通常分为两部分：递归的方式和递归的终止条件（最小事件的解）。这两个部分是递归的关键！

递归的方式，就是指递归公式，即对问题的分解，同时也是向递归终止条件收敛的规则。而递归的终止条件通常就是得出的最小事件的解。递归终止条件的作用就是不让递归无限地进行下去，最后必须要能“停”下来。

综上所述，使用递归必须要满足的两个条件就是：

• 要有递归公式。
• 要有终止条件。

如何学习递归

大多数人在学习递归的时候一般都会有一个问题，“怎么知道什么时候可以用递归，什么时候不可以用递归？”

很多人在学习递归的时候都会有这个困惑。虽然递归的思想也掌握了，也知道使用递归必须要具备两个条件，但就是不会用，无法用递归解决新的问题。

那么到底怎么知道一个问题是否可以用递归解决呢？其实，一个问题是否可以用递归来解决，这是一个数学问题，这个问题不需要我们考虑，换句话说，不要去考虑一个问题能不能用递归解决，我们所要做的就是掌握那些已知的、非常经典的递归算法。

递归和循环的关系

递归和循环存在很多关系。理论上讲，所有的循环都可以转化成递归，但是利用递归可以解决的问题，使用循环不一定能解决。比如编写树和图的程序就必须用递归，虽然循环也可以实现，但那样做绝对是程序员的噩梦。

循环又称迭代。递归算法与迭代算法设计思路的主要区别在于：函数或算法是否具备收敛性！当且仅当一个算法存在预期的收敛效果时，采用递归算法才是可行的。否则就不能使用递归算法。所谓收敛性就是指要有终止条件，不能无休止地递归下去。

递归的优缺点

递归的优点是简化程序设计，结构简洁清晰，容易编程，可读性强，容易理解。在很多情况下使用递归是必要的，它往往能把复杂问题分解为更简单的步骤，而且能够反映问题的本质。我们一开始可能发现递归理解起来也不容易，这是因为我们的“见识”太少了！等将来学习树和图的时候你才能真正领会到递归是多么的“好理解”！

又比如汉诺塔，用递归的话基本上可以理解，但是如果不用递归而用循环的话，程序根本不知道从何处着手！

但是递归的缺点也很明显：速度慢，运行效率低，对存储空间的占用比循环多。严格讲，循环几乎不浪费任何存储空间，而递归浪费的空间实在是太大了，而且速度慢。

因为递归是用栈机制实现的，每深入一层都要占用一块栈数据区域。对嵌套层数深的一些算法，递归就会显得力不从心，最后都会以内存崩溃而告终。而且递归也带来了大量的函数调用，这也有许多额外的时间开销。函数调用要发送实参，要为被调函数分配存储空间，还要保存返回的值，又要释放空间并将值返回给主调函数，这些都太浪费空间和时间。

虽然递归有那么多缺点，但是没有办法，有些问题太复杂，不用递归就解决不了！

与递归相比，循环的缺点是不容易理解，遇复杂问题时编写困难。但它的优点是速度快、效率高、不浪费空间。循环的运行时间只因循环次数增加而增加，没有其他额外开销，空间上同样。

对于初学者而言，我们所遇到的递归算法一般都比较简单，能用递归解决的一般都能用循环解决，所以初学编程的时候大家不要总想着使用递归。

下面给大家编写几个程序，列举几个例子，主要通过例子让大家对递归有一个了解。

1) 用递归求 n 的阶乘。

n！也可以写成 n×(n–1)！，这就是递归公式。

# include <stdio.h>
long Factorial(int n);  //函数声明
int main(void)
{
    int n;
    printf("请输入n的值:");
    scanf("%d", &n);
    printf("%d! = %ld\n", n, Factorial(n));
    return 0;
}
long Factorial(int n)  //阶乘的英文为factorial
{
    if (n < 0)
    {
        return -1;
    }
    else if (0==n || 1==n)  /*关系运算符的优先级大于逻辑运算符的优点级, 所以不用加括号*/
    {
        return 1;
    }
    else
    {
        return n * Factorial(n-1);
    }
}

输出结果是：
请输入n的值:10
10! = 3628800

n 的值不要太大，不然容易溢出，long 类型也放不下。

2) 用递归实现 1+2+3+…+100 的和

求和的递归公式跟求阶乘的递归公式很相似：Sum(n)=n+Sum(n–1)。

# include <stdio.h>
int Sum(int n);  //函数声明
int main(void)
{
    int n;
    printf("请输入n的值:");
    scanf("%d", &n);
    printf("sum = %d\n", Sum(n));
    return 0;
}
int Sum(int n)
{
    if (n <= 0)
    {
        return -1;
    }
    else if (1 == n)
    {
        return 1;
    }
    else
    {
        return n+Sum(n-1);
    }
}

输出结果是：
请输入n的值:100
sum = 5050

3) 用递归求斐波那契数列。

所谓斐波那契数列是指数列中每一个数值都是其前两个数值之和，即：

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368……

# include <stdio.h>
long Fibonacci(int n);  //函数声明
int main(void)
{
    int n;
    printf("请输入n的值:");
    scanf("%d", &n);
    printf("第n项的值为：%ld\n", Fibonacci(n));
    return 0;
}
long Fibonacci(int n)
{
    if (n < 0)
    {
        return -1;
    }
    else if (0 == n)
    {
        return 0;
    }
    else if (1 == n)
    {
        return 1;
    }
    else
    {
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
}

输出结果是：
请输入n的值:21
第n项的值为：10946

通过上面这几个程序我们发现递归都有一个共同的特点，就是递归公式全部都是写在 return 语句后面的，而且最小事件的解都会返回一个具体的值。如果最小事件的解不返回一个具体值的话，那么递归就无法停下来。