斐波那契递归：一个调用分两叉

斐波那契数列 1, 1, 2, 3, 5, 8……从第 3 项起，每项是前两项之和。② 里用循环算过，用递归写更像定义本身：

#include <stdio.h>

int fib(int n)
{
    if (n == 1 || n == 2)
        return 1;
    return fib(n - 1) + fib(n - 2);
}

int main(void)
{
    printf("%d\n", fib(6));
    return 0;
}

和前一关不同：这里每一层要调用两次自己，调用会像树一样分叉，有些项会被重复计算。

程序输出【0】。如果改成计算 fib(5)，fib(3) 会被调用【1】次，fib(2) 会被调用【2】次。