1、 第一题（引子）：输出菲波那切数列的第N项。
　　斐波那契数列含义（百度百科）：
　　指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
　　在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）

递归
def fibonacci(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num > 1:
		return fibonacci(num - 2) + fibonacci(num - 1)
	
我们计算n为4的情况：那么我们需要做如下的计算：
Fibonacci(4) = Fibonacci(3) + Fibonacci(2);
= Fibonacci(2) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);
= Fibonacci(1) + Fibonacci(0) + Fibonacci(1) 
	+ Fibonacci(1) + Fibonacci(0);

看看，多做了多少计算。2 计算了 2次，1 计算了5次，0计算了3次。
正常来说我们计算4次就可以了吧。这样相当于多做了4次

·

非递归方式

延伸：
青蛙跳
　　2. 一只青蛙一次可以跳上1级台阶，也可以跳上2级。
　　　　求该青蛙跳上一个n级的台阶总共有多少种跳法。
　　　　（先后次序不同算不同的结果）。

如果n=1，只有一种跳法，那就是1
如果n=2，那么有两种跳法，2，[1,1]
如果n=3，那么有三种跳法，[1,1,1],,[1,2],[2,1]
如果n=4，那么有五种跳法，[1,1,1,1],[1,1,2],[1,2,1],[2,1,1],[2,2]
如果n=5，那么有八种跳法:
[1,1,1,1,1],[1,1,1,2],[1,1,2,1],[1,2,1,1],[2,1,1,1],[2,2,1],[2,1,2],[1,2,2]

结果为1，2，3，5，8  这不特么是斐波那切数列嘛

·

递归：
def jump(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 2
	elif num > 2:
		return jump(num - 2) + jump(num - 1)

·

非递归：

青蛙变态跳
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

f(n) 
= f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)
= f(0) + f(1) + f(2) + f(3) + ... + f(n-2)+f(n-1)

f(n-1) 
= f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) 
= f(0) + f(1) + f(2) + f(3) + ... + f(n-2)

so  f(n)=2*f(n-1)

递归：
def jump_1(num):
	if num == 1:
		return 1
	elif num > 1:
		return 2 * jump_1(n - 1)

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个m级的台阶总共有多少种跳法。

先列多项式：
f(n) =  f(n-1) + f(n-2) + f(n-3) + ... + f(n-m)
f(n-1) =   f(n-2) + f(n-3) + ... + f(n-m) + f(n-m-1)
化简得：f(n) = 2f(n-1) - f(n-m-1)

递归
def jump_2(n , num):
	if n > m:
		return 2 * jump_2(n - 1, m) - jump_2(n - 1 -m, m)
	elif n == 1:
		return 1
	elif n > 1:
		return 2 * jump_2(n - 1, n)