# 多层递归函数多层递归的调用关系比较复杂，整体上看起来像一颗倒立的树：对于双层递归，树的每个节点有两个分叉；对于三层递归，树的每个节点有三个分叉；以此类推…… 下面我们以「求菲波那契数」为例来演示双层递归，更多层次的递归请读者自己探索。菲波那契数就是一个数列，数列中每个数的值就是它前面两个数的和，这种关系常常用以下形式进行描述： $$ Fib(n) = \begin{cases} 1, n<=2\\ \\ Fib(n-1)+Fib(n-2), n>2 \end{cases} $$ 代码如下 ```c #include #include //递归计算斐波那契数 long fib(int n); int main(int argc, char *argv[]){ int a; printf("Input a number: "); scanf("%d", &a); printf("Fib(%d) = %ld\n", a, fib(a)); system("pause"); return 0; } long fib(int n){ if(n<=2){ return 1; } else{ return fib(n-1)+fib(n-2); } } ``` 当 n≥2 时，每次调用 fib(n) 都要等待 fib(n-1) 和 fib(n-2) 的结果，这种调用关系看起来就像一棵倒立的二叉树。双层递归的调用关系和数据结构中二叉树的结构完全吻合，所以双层递归常用于二叉树的遍历。单层递归每次只等待一个函数的结果，双层递归每次要等待两个函数的结果，这就是它们之间最本质的区别。