【Python】Recursion递归 典型问题

这里是一个刚刚上手Python的小白整理的一些题型。大部分题目来自平时上课的例题及习题，在此稍作整理，以供复习之用。
因为平时全英文，有些专有名词不知道中文名，就直接用英文代替啦～

1. 二分法找有序数列指定值

写一个程序binary_search(x, y), 输入一个list x (你可以假设里面的数据已经按升序排列) 然后输入想要查找的数据y，使得函数返回y的index，或者当y不属于x时返回 “Not found”.

def binary_search(x,y):
    a = 0
    b = len(x) #如果这里打的是‘len(x)-1’，那么如果要查找最后一个数就会陷入死循环
    c = (a+b)//2
    if y not in x:
        return 'Not found'
    while x[c] != y:
        if x[c] < y:
            a = c
        elif x[c] > y:
            b = c
        c = (a+b)//2
    return c

这个问题如果以问法的话就只能写loop的函数，但其实它也可以用recursion解：

def binary_search(min, max, d, n): '''初始mid=0, max=len(d)'''
    mid = (min+max)//2
    if n not in d:
        return 'Not found'
    elif d[mid] < n:
        return binary_search(mid, max, d, n)
    elif d[mid] > n:
        return binary_search(min, mid, d, n)
    else:
        return mid

2. 字符串（非重复）全排列

def permutation(array):
    if len(array) <= 1:
        return [array]
    res = []
    for i in range(len(array)):
        s = array[:i] + array[i+1:] #每次拿出一个元素
        p = permutation(s) #将剩下元素全排列
        for x in p:
            res.append(array[i:i+1]+x) #将该元素插到剩下元素后面

（或者要做有重复的也很简单，再写一个function把重复的去掉即可）

3. 爬楼梯问题

1）假设一共有n级台阶，每次可以跨1步或3步，求要爬完这一段台阶一共有多少种可能

（可以看成是斐波那契数列）

def func(n):
    if n <= 2:
        return 1
    elif n == 3:
        return 2
    elif n > 3:
        return func(n-1) + func(n-3)

2）假设一共有n级台阶，每次可以跨1步或3步，列举要爬完这一段台阶的所有可能

def func(n):
    res = []
    if n == 1:
        return '1'
    elif n == 2:
        return '11'
    elif n == 3:
        return ['111', '3']
    elif n > 3:
        for i in func(n-1):
            res.append(i + '1')
        for i in func(n-3):
            res.append(i + '3')
        return res

4. Tower of Hanoi

1）假设一共有n块圆盘，求总共需要移动的次数

def han(n):
    k = 0
    if n == 1:
        k += 1
    elif n > 1:
        k += 2*han(n-1) + 1
    return k

2）假设一共有n块圆盘，求每次移动的步骤

def han(disc, frm, to, temp):
    if disc == 1:
        print('move disc' , 1, 'from', frm, 'to', to)
    elif disc > 1:
        han(disc-1, frm, temp, to)
        print('move disc' , disc, 'from', frm, 'to', to)
        han(disc-1, temp, to, frm)

5. 列举一个字符串中每一个字母的大小写全排列

Write a program to read a string input and then output a list of all possible case permutations of the string.（比如“Ab”，就有“ab，Ab，aB，AB”四种可能）

def case_permutation(array):
    res = []
    if len(array) <= 1:
        res.append(array.lower())
        res.append(array.upper())
        return res
    else:
        s = array[0]
        array = array[1:]
        p = case_permutation(array)
        for x in p:
            res.append(s.lower()+x)
            res.append(s.upper()+x)
    return res

6. 判断回文

def is_pal(line):
    n = len(line)
    if n <= 1:
        return True
    elif n <= 3:
        if linr[0] == line[n-1]:
            return True
        else:
            return False
    elif n > 3:
        if line[0] == line[n-1]:
            return is_pal(line[1:n-1]) '''删去第一个和最后一个字符'''
        else:
            return False

7. 寻找一个set的power set

（这里我自动默认已经把set转换成了一个list）

def power(s):
    res = []
    if len(s) == 1:
        res.append([s[0]])
        res.append([])
    elif len(s) > 1:
        for i in power(s[1:]):
            res.append(i)
            res.append(i+[s[0]]) 
    return res

目前暂时整理了这么多，但只要把套路摸透，就会发现所有的recursion核心思路基本都一样
祝大家考试顺利，过三爆四～～