4.1 引言

递归是程序设计中常用的解决问题的方法，它在数据结构的构造和算法设计中都要重要的应用。
总结出利用递归求解问题的基本步骤，建立递归思维的习惯。
求解递归函数的二个基本方法，为分析递归算法的时间复杂度建立数据基础。

4.2 递归的组成结构

4.2.1 如何筹集巨款

代码 4.1 筹集善款的递归算法

def collect_contributions(n): #n 为需要筹集的款数
    if (n=<100):
        return 100 #需要此人捐出100元
    else:
        #寻找10个朋友
        friends = find_frends()
        for f in friends:
            #从这10个朋友中分别募集 n/10 元
            sum += collect_contributions(n/10)
    return sum #返回从10个朋友募集到的资金

4.2.2 上线与下线

4.3 递归算法的执行

代码 4.2 斐波那契数的递归算法

def fib_rec(n):
    if n==0 or n == 1:
        return n
    else:
        return fib_rec(n-1) + fib_rec(n-2)
if __name__=='__main__':
    num = 24
    print('{0:5} ==>{1:10d}'.format('fib('+str(num)+')' ,fib_rec(num)))

4.3.1 跟踪函数的执行

递归算法求解斐波那契数的时间复杂度是指数规模增长，想想如何降低复杂度来求解斐波那契数。

4.4 利用递归算法求解问题

4.4.1 回文判断

代码 4.3 回文算法

def is_palindrome(s):
    if len(s) =< 1:
        return True
    else:
        # if s[0] == s[-1]:
        #     is_palindrome(s[1:-1])
        # else:
        #     return False
        return s[0] ==s[-1] and is_palindrome(s[1:-1])

代码 4.4 判断中文字符串的回文算法

#coding=uft-8
def is_palindrome(s):
    if len(s) <= 1:
        return True
    else:
        return s[0] == s[-1] and is_palindrome(s[1:-1])
if  __name__=="__main__":
    s = u'上海自来水来自海上'
    if(is_palindrome(s)):
        print("\""+s+"\""+"是回文")
    else:
        print("\""+s+"\""+"不是回文")

4.4.2 全排列

代码 4.5 产生全排列的递归算法

def permutation(str):
    result = []
    if len(str) <=1:
        return str
    else:
        for i in range(len(str)):
            for s in permutation(str[0:i]+str[i+1:len(str)]):
                result.append(str[i] +s )
    return result
if __name__=="__main__":
    print(permutation('ABC'))

4.4.3 汉诺塔问题

代码 4.6 汉诺塔算法

def hanoi(n,source,target,helper):
    if n == 1:
        moveSingleDesk(source,target)  #边界条件
    else:
        hanoi(n-1,source,helper,target) #将n-1 个盘从A移到 C
        moveSingleDesk(source,target) # 将A中最大的一个盘移到 B
        hanoi(n-1,helper,target,source) #将 n-1 个盘从 C 移到 B


def moveSingleDesk(source,target):
    disk = source[0].pop()
    print("moving "+ str(disk) + " from " + source[1] +" to " + target[1])
    target[0].append(disk)

if __name__=="__main__":
    A = ([4,3,2,1],"A")
    B = ([],"B")
    C = ([],"c")
    hanoi(len(A[0]),A,B,C)

4.4.4 雪花曲线

代码 4.7 绘制雪花曲线

import turtle
def koch(t,order,size):
    if order == 0: # 边界条件
       t.forward(size) 
    else:
        koch(t,order-1,size/3) #递归调用
        t.left(60)            # 笔转60度
        koch(t,order-1,size/3) #递归调用
        t.right(120)            # 笔转120度
        koch(t,order-1,size/3)   #递归调用
        t.left(60)              # 笔转60度
        koch(t,order-1,size/3)  #递归调用
if __name__=="__main__":
    t = turtle
    order = 2
    size = 9
    koch(t,order,size)

4.5 递归函数的求解

4.5.1 替换法

4.5.2 主分析法

4.6 小结