死磕递归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)$等等，所以，最重要的就是如何分析问题得到递推公式。