递归

1、最简单的一个递归，以相反的顺序打印字符串

void print_reverse (const char * s)
{
    if (NULL == s || '\0' == *s)
        return;
    print_reverse (s + 1);
    putchar( *s );
}

2、原地反转字符串

void reverse_str (char s[], int n)
{
    if (NULL == s)
        return;
    char tmp;
    if(n >= 2)
    {
        tmp = s[0];
        s[0] = s[n-1];
        s[n-1] = tmp;
        reverse_str(s+1, n-2);
    }
}

3、求斐波那契数列的第 n 项
数列的定义如下：
f(0) = 0;
f(1) = 1;
f(n) = f(n - 1) + f(n - 2); ( n > 1)
先用递归的写法：

func f(n int) int {
    if n < 2 {
        return n
    } else {
        return f(n - 1) + f(n - 2)
    }
}

再改为循环的写法：

func f(n int) int {
    if n < 2 {
        return n
    }
    var f0, f1, fn int
    f0,f1 = 0,1
    for i := 1; i < n; i++ {
        fn = f0 + f1
        f0 = f1
        f1 = fn
    }
    return fn
}

因为Go或Python可以同时给多个变量赋值，所以可以这样简写：

func f(n int) int {
    if n < 2 {
        return n
    }
    f0, f1 := 0, 1
    for i := 1; i < n; i++ {
        f0, f1 = f1, f0 + f1
    }
    return f1
}

为什么要改成循环的写法呢？因为这里用递归会有大量重复计算：

                        f(5)
             f(4)         +        f(3)
        f(3)   +    f(2)       f(2)  +  f(1)
   f(2)  +  f(1)  f(1)+f(0)  f(1)+f(0)
f(1)+f(0)

展开之后相当于一棵二叉树，总的计算次数取决于二叉树的高度，以及每层的节点数，下面简单的计算一下：

高度的问题：
因为最左边每次只减 1，深度最深，大约是 n，
最右边每次减 2，深度最浅，大约是n/2，
而中间的部分介于两者之间，所以取值范围是n/2 <= h <= n，

每层的数量的问题：
第 1 层只有 1 个，也就是2⁰，
第 2 层有 2 个，即 2¹，
第 3 层有 4 个，即 2²，
第 k 层有 2 ^k-1 次方。

所以当 h=n，总的结点数为

根据等比数列求和公式，

当 h=n/2，总的结点数为

根据等比数列求和公式，

所以，如果用递归的方法，时间复杂度就介于 O(2ⁿ) 和 O(2^n/2) 之间；
而用循环的方法，时间复杂度是 O(n)，所以需要使用循环来写。

4、求 x 的 n 次幂
递归的写法：

func myPow(x float64, n int) float64 {
    if n == 0 {
        return 1
    }
    if n < 0 {
        return 1 / myPow(x , -n)
    }
    if n % 2 == 1 {
        return x * myPow(x , n-1)
    }
    return myPow(x*x , n/2)
}

模 2 和除以 2 都可以改为位运算，递归改为循环的写法：

func myPow(x float64, n int) float64 {
    if n < 0 {
        x = 1/x
        n = -n
    }
    pow := 1.0
    for n > 0 {
        if n & 1 == 1 {
            pow *= x
        }
        x *= x
        n >>=1
    }
    return pow
}

5、细胞分裂问题

（1）描述
有1个细胞，每1个小时分裂1次，1次分裂出1个子细胞，每个细胞能活3个小时。
求第n个小时有多少个细胞？
（2）分析
假设细胞在每个小时分别是：状态a，状态b，状态c；

设 f(n) 为第 n 小时的细胞数量，

设 fa(n) 为第 n 小时的 a 细胞数量，

设 fb(n) 为第 n 小时的 b 细胞数量，

设 fc(n) 为第 n 小时的 c 细胞数量，

则 f(n) = fa(n) + fb(n) + fc(n)。

fa(n) = fa(n-1)+ fb(n-1) + fc(n-1)，当 n = 1，fa(1) = 1

fb(n) = fa(n-1)，当 n=1，fb(n) = 0；

fc(n) = fb(n-1)，当 n=1,2，fc(n) = 0；

f(n) = fa(n) + fb(n) + fc(n)

（3）实现

#include <stdio.h>

int fa(int n);
//  n 小时 b 阶段的细胞数量
int fb(int n)
{
    if(n==1)
    {
        return 0;
    }
    else
    {
        return fa(n-1);
    }
    
}

//  n 小时 c 阶段的细胞数量
int fc(int n)
{
    if(n==1 || n==2)
    {
        return 0;
    }
    else
    {
        return fb(n-1);
    }
}

//  n 小时 a 阶段的细胞数量
int fa(int n)
{
    if(n==1)
    {
        return 1;
    }
    else
    {
        return fa(n-1)+fb(n-1)+fc(n-1);
    }
}

int f(int n)
{
    return fa(n) + fb(n) + fc(n);
}

int main(void)
{
    printf("f( %d ) = %d \n", 1, f(1) );
    printf("f( %d ) = %d \n", 2, f(2) );
    printf("f( %d ) = %d \n", 3, f(3) );
    printf("f( %d ) = %d \n", 4, f(4) );
    return 0;
}