递归

递归是一种解决问题的方法，它把一个问题分解为越来越小的子问题，直到问题的规模小到 可以被很简单直接解决。而递归函数就是一种调用自身的函数。

递归求和

1
2
3
4
5
6
7
8
9
10
11
# 列表递归求和方法一
def listSum(lst):
    if len(lst) == 1:
        return lst[0]
    else:
        return lst[0] + listSum(lst[1:])

# 列表递归求和方法二
def iterSum(arr):
    head, *tails = arr
    return head + iterSum(tails) if tails else head

递归三大定律

  • 递归算法必须要递归地调用自己
  • 递归算法必须有一个基本结束条件
  • 递归算法必须改变自己的状态并向基本结束条件靠近
    1
    2
    3
    4
    5
    6
    7
    # 递归转换整数到字符串
    def to_str(n, str):
        convert_str = '0123456789ABCDEF'
        if n < base:
            return convert_str[n]
        else:
            return to_str(n//base, base) + convert_str[n%base]
1
2
3
4
5
6
# 写一个函数，接受一个字符串作为参数，并返回一个反向的新字符串。
def reverse(s):
    if len(s) == 1:
        return s
    else:
        return reverse(s[1:]) + s[0]

总结： 递归的逻辑就是利用优美的程序把问题分解为更小更简单的子问题来解决。

谢尔宾斯基三角形

汉诺塔问题

动态规划