C语言多层递归函数(最烧脑的一种递归)

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

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

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

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

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

运行结果=

Input a number: 7↙

Fib(7) = 13

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

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

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

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