首页 > 编程笔记

函数的递归调用,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 语句后面的,而且最小事件的解都会返回一个具体的值。如果最小事件的解不返回一个具体值的话,那么递归就无法停下来。

推荐阅读