Recursion 递归

Usually recursion involves a function calling itself. While it may not seem like much on the surface, recursion allows us to write elegant solutions to problems that may otherwise be very difficult to program.

递归的三定律

A recursive algorithm must have a base case.
A recursive algorithm must change its state and move toward the base case.
A recursive algorithm must call itself, recursively.
base case 是指递归算法需要有一个标识终止递归的状态，避免无限递归循环下去。而这个 base case 就是一个“最小直接解决问题”的单位。
第二条定律是指每次递归都需要向 base case 更进一步。
递归必须是自我调用，这正是递归的定义。

简单的例子

反转字符串



In [4]:

    
def reverse(s):
    if len(s) == 0:  # 有一个 base case 来终止递归
        return ''
    else:
        return s[-1] + reverse(s[:-1])  ## 满足第二、三条定律，每次递归都更进一步，并且是自我调用。

assert reverse('apple') == 'elppa'

检查是否为回文字符串（正序与倒序一致）



In [8]:

    
import re

def removeWhite(s):
    return re.sub(r'[\W]', '', s)

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

assert isPal(removeWhite("x")) is True
assert isPal(removeWhite("radar")) is True
assert isPal(removeWhite("hello"))is False
assert isPal(removeWhite(""))is True
assert isPal(removeWhite("hannah")) is True
assert isPal(removeWhite("madam i'm adam")) is True

递归实际就是压栈的操作。将递归执行的函数依次压入栈中，然后再依次弹出结果。

更复杂的例子

汉诺塔

汉诺塔是一个非常典型的利用递归的思想解决问题的例子：

如果你不知道如何把 n 个盘子挪过去，那可以先把 n-1 个盘子挪到中间位置，再把 1 个盘子挪到最后的位置，最后把中间的 n-1 个盘子挪到指定位置；
如果你不知道如何挪 n-1 个盘子，那就先挪 n-2 个... n-3 个...
以此类推，最终你只要知道如何把一个盘子挪过去就可以解决问题了。

Move a tower of height-1 to an intermediate pole, using the final pole.
Move the remaining disk to the final pole.
Move the tower of height-1 from the intermediate pole to the final pole using the original pole.



In [3]:

    
def moveTower(height,fromPole, toPole, withPole):
    if height >= 1:
        moveTower(height-1,fromPole,withPole,toPole)
        moveDisk(fromPole,toPole)
        moveTower(height-1,withPole,toPole,fromPole)

def moveDisk(fp,tp):
    print "moving disk from",fp,"to",tp

moveTower(3,"A","B","C")









    



moving disk from A to B
moving disk from A to C
moving disk from B to C
moving disk from A to B
moving disk from C to A
moving disk from C to B
moving disk from A to B