递归：递推公式

大家好，欢迎来到IT知识分享网。

1. 递推公式

证明$f(n)=5^n+3$可以被4整除
先看几个具体的case，看看能不能被4整除

查看了几个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开始计算

也就是说我想要求解$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 

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

也就是说，我们现在只需要求解$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. 斐波那契数列

你会发现从前往后算是非常复杂的，这个问题可以从后往前思考。例如当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上面去。

可以很容易的写成递归方法

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 

5. 小总结

上面的递推问题，本质都是不断减小问题规模，要求$f(n)$，先求出较小规模的$f(n-1),f(n//2)$等等，所以，最重要的就是如何分析问题得到递推公式。