vlambda博客
学习文章列表

“多层递归”是我自己起的名字，意思是在一个函数里面多次调用自己。

多层递归的调用关系比较复杂，整体上看起来像一颗倒立的树：对于双层递归，树的每个节点有两个分叉；对于三层递归，树的每个节点有三个分叉；以此类推……

下面我们以「求菲波那契数」为例来演示双层递归，更多层次的递归请读者自己探索。

菲波那契数就是一个数列，数列中每个数的值就是它前面两个数的和，这种关系常常用以下形式进行描述：


这种形式很容易让人使用递归，下面给出C语言代码实现：

#include <stdio.h>//递归计算斐波那契数long fib(int n) { if (n <= 2) { return 1; } else { return fib(n - 1) + fib(n - 2); }}int main() { int a; printf("Input a number: "); scanf("%d", &a); printf("Fib(%d) = %ld\n", a, fib(a)); return 0;}

运行结果：

Input a number: 7↙
Fib(7) = 13

当 n≥2 时，每次调用 fib(n) 都要等待 fib(n-1) 和 fib(n-2) 的结果，这种调用关系看起来就像一棵倒立的二叉树，如下图所示：

双层递归的调用关系和数据结构中二叉树的结构完全吻合，所以双层递归常用于二叉树的遍历。

单层递归每次只等待一个函数的结果，双层递归每次要等待两个函数的结果，这就是它们之间最本质的区别。

如果你觉得这还不够复杂，还可以将双层递归和尾递归结合起来，我相信这足够杀死你的一片脑细胞了，有兴趣的话可以自己探索，我就不奉陪了 ^_^。