算法第一讲递归(recursion)

递归是一种通过将原问题分解成同类的子问题来解决问题的方法。通常涉及到对函数对函数自身的调用。

所有的递归算法都应该：

  1. 有一个base case，是很好解决的子问题
  2. 分解原问题，向着1中的base case去靠近
  3. 调用函数自身

Anything you can do with recursion, you can also do it with a loop.

递归只是一种解决问题的思路。递归的解法有时更容易理解。

值得注意的一点：在用递归的思想解决问题时，因为函数调用的开销、冗余计算造成的程序效率低。这是在实现是应该多考虑的[1]。

目录

汉诺塔问题

思路：将N-1个盘子从From移动到With；再把最大的盘子移动到To；最后把剩下的N-1个盘子从With移动到To。把N个盘子的问题，转换成两了N-1个盘子的问题。

from __future__ import print_function

def hanoi(fromPole, toPole, withPole, height):
    if height > 1:
        hanoi(fromPole, withPole, toPole, height-1)
        move(fromPole, toPole)
        hanoi(withPole, toPole, fromPole, height-1)

def move(fromPole, toPole):
    print('move disk from', fromPole, 'to', toPole)

迷宫问题

思路：将找到一条从起始点到终点的路径，转换为，从起始点的上下左右任一点找到一条到终点的路径。走过的点被标记下来，以免造成无尽的循环。

def find_a_path(maze, start_row, start_column):
    maze.update_postion(start_row, start_column, None)

    if maze[start_row][start_column] in (OBSTACLE, TRIED):
        return False
    if maze.is_exit(start_row, start_column):
        maze.update_postion(start_row, start_column, PART_OF_PATH)
        return True

    maze.update_postion(start_row, start_column, TRIED)

    # 这里+1，-1在列表中不会出错了？这里只是为了表示向上下左右移动，可以重写maze类的[]
    found = find_a_path(maze, start_row-1, start_column) or \
            find_a_path(maze, start_row, start_column+1) or \
            find_a_path(maze, start_row-1, start_column) or \
            find_a_path(maze, start_row, start_column-1)

    if found:
        maze.update_postion(start_row, start_column, PART_OF_PATH)
    else:
        maze.update_postion(start_row, start_column, DEAD_END)
    return found

参考资料：

扩展阅读[2]：

注[1]: 递归优化（最简单如尾递归）。

注[2]: 递归的思想还可以用于二叉树、排序等。