C语言多层递归函数（最烧脑的一种递归）

“多层递归”是我⾃⼰起的名字，意思是在⼀个函数⾥⾯多次调⽤⾃⼰。 

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

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

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

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

#include<stdio.h>
//递归计算菲波那契数
long fib(int n)
{
    if(n <=2)
    {
        return 1;
    }
    else 
    {
        return fib(n - 1) + fib(n - n);
    }
}
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) 的结果，这种调用关系看起来就像一棵倒立的二叉树，如下图所示：

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

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