死磕遞歸1：遞推公式

1. 遞推公式

證明$f(n)=5^n+3$可以被4整除
先看幾個具體的case，看看能不能被4整除

$n$	$f(n)=5^n+3$
$n=1$	$f(1)=5^1+3=8$
$n=2$	$f(2)=5^2+3=28$
$n=3$	$f(3)=5^3+3=128$

查看了幾個case發現都是可以被4整除的，那麼如何證明任意一個n都可以讓$5^n+3$被4整除呢？前面通過實際的數據錶明n=3的時候是可以被4整除的，那麼n=4可以被4整除嗎
$$\begin{array}{rl}f(4)& =5^4+3\\ & =5\times 5^3+3\\ & =4\times 5^3+5^3+3\\ & =4\times 5^3+f(3)\end{array}$$

可以發現$4\times 5^3$可以被4整除，而且$f(3)$也是可以被4整除的，因此$f(4)$可以被4整除。更一般的有遞推公式
$$\begin{array}{rl}f(k+1)& =5^{k+1}+3\\ & =5\times 5^k+3\\ & =4\times 5^k+5^k+3\\ & =4\times 5^k+f(k)\end{array}$$

遞推公式已經被我們寫出來了，可以看到如果$f(k)$可以被4整除，那麼$f(k+1)$就一定可以被4整除。我們從1開始計算

• 1可以被4整除，那麼一定有2可以被4整除
• 2可以被4整除，那麼一定有3可以被4整除
• …

依次進行下去，也就是說任意一個整數都可以符合。

2. 如何求解$n!$

再看一個問題，如何求解$n!$，這個問題也非常的簡單，我們直接從1開始一直乘到n就可以得到了

res = 1
for i in range(1,n+1):
    res *= i

我們這裏可以考慮遞歸，說白了就是求遞推公式，我們也從最簡單的n=1開始計算

$n$	$f(n)=n!$
$n=1$	$f(1)=1$
$n=2$	$f(2)=1\ast 2$
$n=3$	$f(3)=1\ast 2\ast 3$
$n=4$	$f(4)=1\ast 2\ast 3\ast 4$
$n=5$	$f(5)=1\ast 2\ast 3\ast 4\ast 5$

更一般的遞推公式有
$$f(n)=f(n-1)\ast n$$

也就是說我想要求解$f(n)$，那麼我只需要把$f(n-1)$求解出來即可，但是為了求解$f(n-1)$，我需要把$f(n-2)$求解出來，說白了就是不斷的套娃。簡單看一下$f(6)$是如何計算
$$\begin{array}{rl}f(6)& =1\ast 2\ast 3\ast 4\ast 5\ast 6\\ & =f(5)\ast 6\\ & =f(4)\ast 5\ast 6\\ & =f(3)\ast 4\ast 5\ast 6\\ & =f(2)\ast 3\ast 4\ast 5\ast 6\\ & =f(1)\ast 2\ast 3\ast 4\ast 5\ast 6\\ & =1\ast 2\ast 3\ast 4\ast 5\ast 6\end{array}$$

老實說這有種脫褲子放屁的感覺，還不如直接從1開始直接乘到n，這個case是沒有任何問題的，不過越往後case會越複雜，也越會接近遞歸。我們先用遞歸的方式寫出來

def f(n):
	if n == 1:return 1
    return f(n-1)*n

3. 如何求解$x^n$

這個問題也是非常的簡單，我們依然通過循環就可以解决

def f(x,n):
    res = 1
    for _ in range(n):
    	res *= x
    return res

同樣可以寫出遞推公式
$$f(n)=f(n-1)\ast x$$
寫出他的遞歸方法

def f(x,n):
	if n == 0:
		return 1
	return f(x,n-1)*x

同樣這個case也是脫褲子放屁，明明可以用循環解决為什麼要考慮使用遞歸呢？因為有一種巧妙的解决方法，我們把遞歸公式改一改
$$f(n)=\{\begin{array}{ll}{f}^2(\lfloor \frac{n}{2}\rfloor )& n\%2==0\\ f^2(\lfloor \frac{n}{2}\rfloor )\ast x& n\%2==1\end{array}$$
這個方法不是我想出來的，但是看到之後覺得非常的巧妙。我們看一下$f(13)$怎麼求。

$f(13)$	$f^2(6)\ast x$	$13\%2=1$
$f(6)$	$f^2(3)$	$6\%2=0$
$f(3)$	$f^2(1)\ast x$	$3\%2=1$
$f(1)$	$f^2(0)\ast x$	$1\%2=1$
$f(0)$	$1$	base

也就是說，我們現在只需要求解$f(1),f(3),f(6),f(13)$只需要求解4次就可以得到結果了，而如果使用循環的話，我們則需要求解13次，高下立判。
這個case說明了一個問題，不同的遞推公式，會得到不同的求解複雜度。在這個case中，常規的遞推公式是一步一步的縮小問題求解規模的，也就是得到$f(n)$和$f(n-1)$的關系，然後每次减少1來不斷縮小問題規模，但是修改之後得到的是$f(n)$和$f(n//2)$的關系，每次是$n//2$的指數方式縮小問題規模。

4. 斐波那契數列

1、樓梯問題：一個階梯共n級，剛開始時人在第1級，若每次只能跨一級或兩級，要走上第n級，共有多少種走法？
假如現在有5階樓梯，我們給每一階樓梯編碼1，2，3，4，5。從最簡單的case開始算起
當n=1時，只有一種方法
當n=2時，可以一步一步跳上去，也可以直接跳上去1-2,2
當n=3時，一步一步跳上去，或者先跳上去兩層，然後再上去一層，或者先走一層再跳上去兩層1-2-3，1-3，2-3

你會發現從前往後算是非常複雜的，這個問題可以從後往前思考。例如當n=4時，如果想要跳上去，只能從2和3兩個臺階跳上來，$f(2)=2,f(3)=3$，所以跳到4階臺階時有$f(4)=f(2)+f(3)=5$種方式。我之前一直考慮的一個問題時，為什麼是兩種方法的相加，為什麼不是想乘或者其他的結合方式呢？我把遞歸樹給繪制了一下，每個圓圈中的值就是這個臺階的名稱，0錶示地面，每一條路徑就是一種跳上去的方法。例如最左側的這條路徑0-1-2-4-5，

• 先跳1步到1上面去，
• 然後再跳1步到2上面去，
• 然後再跳2部跳到4上面去，
• 最後再跳1步跳到5上面去。

可以看到最上面的節點4有5條路徑，節點3有3條路徑，所以節點5總共就有3+5=8條路徑，因此就是相加的關系

根據上面的分析很容易寫成遞推公式
$$f(n)=f(n-1)+f(n-2)$$

可以很容易的寫成遞歸方法

def f(n):
	if n == 1:return 1
	if n == 2:return 2
	return f(n-1)+f(n-2)

如果用遞歸，你會發現一個問題，就是很多節點都重複計算了，因此考慮直接使用循環來解决

def f(n):
	fn1 = 1
	fn2 = 2
	fn = 0
	for i in range(3,n+1):
		fn = fn1+fn2
		fn2 = fn1
		fn1 = fn

2、矩形覆蓋問題：用1×2的小矩形覆蓋2×n的大矩形，總共有多少種方法？
這個問題跟斐波那契數列如出一轍，繪制出來也非常容易理解。假如n=5，如果想要全部填充完成，有兩種方式，一種是將前4個填充完，最後補一個就行，或者就是將前3個填充完，最後需要補兩個

5. 小總結

上面的遞推問題，本質都是不斷减小問題規模，要求$f(n)$，先求出較小規模的$f(n-1),f(n//2)$等等，所以，最重要的就是如何分析問題得到遞推公式。