递归允许函数自我调用
1.线性递归
判断n=0之类的平凡情况以免无限递归而导致系统溢出。这类平凡情况统称为递归基。平凡情况可能有多种,但至少要有一种,且迟早必然会出现。
对列表进行求和:
def sums(ls): if len(ls)<1: return 0 else: return sums(ls[:-1])+ls[-1]
算法sums()每一层次上至多只有一个实例,且它们构成一个线性的次序关系。对应于减而治之策略:递归每深入一层,待求解问题的规模都缩减一个常数,直至最终蜕化为平凡的小问题。
递归算法的复杂度用递归跟踪和递推方程两种方法推导。
2多递归基
针对每一类可能出现的平凡情况,都需设置对应的递归基,故同一算法的递归基可能(显式或隐式的)不止一个。
3多向递归
递归算法中,不仅递归基可能有多个,递归调用也可能有多种可供选择的分支。每一递归实例虽有多个可能的递归方向,但只能从中选择其一,故各层次上的递归实例依然构成一个线性次序关系,这种情况依然属于线性递归。计算power(2,n)=2^n问题:
def power(n): if n==0: return 1 elif n%2==0: return power(n/2)**2 else: return power(int(n/2))**2*2
4尾递归
递归算法所消耗的空间量主要取决于递归深度,故较之同一算法的迭代版,递归版往往需耗费更多空间。在对运行速度要求高、储存空间需精打细算的场合,往往应将递归算法改写成等价的非递归版本。在线性递归算法中,若递归调用在递归示例中恰好以最后一步操作的形式出现,则称作尾递归。属于尾递归形式的算法,均可以简洁的转换为等效的迭代版本。将列表区间内元素倒置:
def rever(ls,lo,hi): if lo<hi: tem=ls[hi] ls[hi]=ls[lo] ls[lo]=tem rever(ls,lo+1,hi-1)
5分而治之
就是将其分解为若干规模更小的子问题,再通过递归机制分别求解,这种分解持续进行,直到子问题规模缩减至平凡情况。与减而治之一样,这里也要求对原问题重新表述,以保证子问题与原问题在接口形式上的一致。通常是将原问题一分为二,称作二分递归。如数组求和:
int sum(int A[],int lo,int hi){ if (lo==hi) return A[lo] else { int mi=(lo+hi)>>1; return sum(A,lo,mi)+sum(A,mi+1,hi); } }