fib (n) = 1　　(n=1)

fib (n) = n*fib(n-1)   (n>1)

// 条件不成立，则继续调用函数并检查条件不满足则继续调用函数...直到函数返回值为1时，再一层层将返回值递归返回上来

// 我们可以用符合条件的尽量简单的实例来剖析那些复杂的算法

例如：5 * 4 * 3 * 2 * 1 = ? 

算了，上面的测试数字太大太复杂了，再选个简单点的例如：3 * 2 * 1 = ?

有人说 2 * 1 = ？ 更简单不过了，我们是要体现递归的特性，所以选择3 * 2 * 1 = ？ 再合适不过了，废话不多，进入正题：

该递归算法源代码为：

uint32_t  fib (uint32_t  n)

{

    if (1==n)

        return 1;

    else 

        return (n * fib (n-1));

}

测试源码为（由于语句嵌入层次比较深，所以我们选择最小的例子来分析，请紧随下列语句分析下去，您一定会豁然开朗！）：

fib (3)

{

    if (1 == 3)

        return 1;

    else

        return (3 * fib(3-1));

}

源码展开为：

初次阅读注释请看注释1，根据后面的注释提示再看注释2：

fib (3)　　/* 注释2： 最终得出 fib(3) = 6，这就是递归算法思想，它像剥洋葱表皮一样一层层深入运算一直到最嫩最好吃的一层，再将返回值一层层返回上来 */

{

    if (1 == 3)

        return 1;

    else

        return (3 * fib(3-1));　　// 注释1：此处n == 传入参数3

        此语句处展开：

　　　     3 * fib (2)　　　　　　　　　　　// 注释2：根据fib(2) = 2, 得出 fib(3) == return (3 * fib(2)) == return (3 * 2) == return 6; 所以fib(3) = 6;

             　　{

             　　     if (1==2)

               　　       return 1;

                　　  else 

                   　　   return (2 * fib(2-1));　　　　　　// 注释2：所以此处返回值为：return (2 * fib (1)) == return  (2 * 1) == return (2);由此得出fib (2) = 2

                    　　  此语句处展开：

　　　　　             2 * fib (1)　　　　　　　　　　　  // 注释2：2 * fib (1) = 2 * 1 = 2，然后往上看到return (2 * fib (2-1));处的注释2

                          　　 {

                                　　if (1==1)  return 1;　　　// 传入参数n为1，条件成立！fib (1) 将返回 1，所以请注意上面 2 * fib (1) 处的“注释2”

                                　　else  return (1 * fib (1)); // 显然不会执行到此处

                           　　}

             　　}

}

数据结构与算法-递归的形象化理解