递归算法中的小Tips
递归算法中的小Tips记忆化尾递归快速幂
递归的基本操作已经在二叉树的笔记中介绍了。但是在做题的过程中发现，递归还是有一些小技巧的。有时候一般的递归还有可能超出时间限制 记忆化
作者：kunkun_1230
递归的基本操作已经在二叉树的笔记中介绍了。但是在做题的过程中发现，递归还是有一些小技巧的。有时候一般的递归还有可能超出时间限制 记忆化
在递归的过程中，尤其是诸如斐波那契数列的计算过程中，由于递归的树形结构，经常会导致多余的计算量。因此，可以通过先建立一个HashMap将计算过的结果存入，便于后续调用。
诸如爬楼梯这道题，引入res后可以减少很多计算时间
def climbStairs(self, n: int) -> int:
res = {}
def recur_fib(n):
if n in res.keys():
return res[n]
if n <= 2:
res[n] = n
else:
res[n] = recur_fib(n-1) + recur_fib(n-2)
return res[n]
return recur_fib(n)
尾递归
尾递归其实不算是一种小trick，只是一种只在最后返回的时候进行一次的递归方式。
不过，递归过程中可能会存在一些计算变量的迭代。
例如，二叉树的最大深度
ps：判断一棵树是否是BST在每次迭代的时候都要加入low和high，而且不断迭代变换。
快速幂在进行累乘的时候，显然你可以一次次的累乘
2n=2∗2∗2...∗22^n = 2*2*2...*22n=2∗2∗2...∗2
显然，这样存在很多的冗余计算，简化一下我们可以写成这样
2n=2n/2∗2n/22^n = 2^{n/2}*2^{n/2}2n=2n/2∗2n/2
这样的话，我们可以每次计算的时候直接计算一半即可。
这样，我们可以写出累乘的代码
class Solution:
def myPow(self, x: float, n: int) -> float:
if n > 0:
return self.help(x,n)
else:
return 1/self.help(x,-n)
def help(self,a,b):
if b == 0: return 1
half = self.help(a,b//2)
if b % 2 == 0:
return half*half
else:
return half*half*a
作者：kunkun_1230
