常见递归问题

1.小鲤鱼

def xiaoliyu(n):
    if n == 0:
        print("我的小鲤鱼", end="")
    else:
        print("抱着", end="")
        xiaoliyu(n-1)
        print("的我", end="")
xiaoliyu(5)  # 抱着抱着抱着抱着抱着我的小鲤鱼的我的我的我的我的我

2.汉诺塔

问题分解：

n个盘子时：
    1.把n-1个圆盘从A经过C移动到B
    2.把第n个圆盘从A移动到C
    3.把n-1个小圆盘从B经过A移动到C

def hanoi(n, A, B, C):
   if n > 0:
       hanoi(n-1, A, C, B)
       print("%s -> %s"%(A, C))
       hanoi(n-1, B, A, C)
hanoi(3, 'A', 'B', 'C')

3.斐波那契数列

斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34....

这个数列从第3项开始，每一项都等于前两项之和。

def fibo(n):
    if n <= 2:
        return n
    else:
        return fibo(n-1)+fibo(n-2)
print(fibo(5))

4.二分查找

从有序列表的候选区data[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。

def binarySearch(li, val, low, high):
    low = 0
    high = len(li) - 1
    while low <= high:
        mid = (low+high) // 2
        if li[mid] > val:
            high = mid - 1
        elif li[mid] < val:
            low = mid + 1
        else:
            return mid
    else:
        return -1

递归版本的二分查找

def binarySearch_rec(li, val, low, high):
    while low <= high:
        mid = (low+high) // 2
        if li[mid] == val:
            return mid
        elif li[mid] > val:
            return binarySearch(li, val, low, mid-1)
        else:
            return binarySearch(li, val, mid+1, high)