关于递归的思考

之前有接触过递归，看到别人写的递归函数的代码，好生羡慕，怎么就能写这么好呢？我怎么就想不到这样写呢？如此等等。

就拿fibonacci函数来说吧，一个普通的函数可能这样写：

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

我看到这个函数的思考方式是这样的：

1. 当n=0时：返回0
2. 当n=1时：返回1
3. 当n=2时：
    1. 首先去调用n=1，返回1
    2. 再去调用n=0，返回0
    3. 把0和1相加返回1
4. 当n=3时：
    1. 调用n=2
        1. 调用n=1，返回1
        2. 调用n=0，返回0
        3. 相加返回1
    2. 调用n=1，返回1
    3. 把1和1相加返回2
5. 等等

想到这我头都要爆了，彻底被人家的函数折服了，看来我是写不成这么好的函数了。

但我转念一想，这个函数的本质是fibnacci序列，我何不回归fibonacci本身呢？fibonacci用数学公式表示应该是这样：

2016-07-07-thinking-in-recursion-formula-of-fibonacci.png

看到公式我恍然大悟，上面那个函数不就是根据这个公式直接翻译的嘛！原来我一直思考都是顺着函数的代码思考，这样肯定会觉得很难,
正确的思考方式应该是从算法出发然后再写代码。

经过了上面的惨痛教训看看我能不能写出正确的fibonacci序列函数，分段函数的公式应该是这样的：

2016-07-07-thinking-in-recursion-formula-of-fibonacci-sequence.png

那么直接写成代码就应该是这样的:

def fib_seq(n):
    seq = []
    if n == 0:
        seq.append(0)
    else:
        seq.extend(fib_seq(n-1))
        seq.append(fib(n))
    return seq

咦，这两个append好像可以合并：

def fib_seq(n):
    seq = []
    if n > 0:
        seq.extend(fib_seq(n-1))
    seq.append(fib(n))
    return seq

哇，原来如此！