Python初学者必会的5个经典递归算法实例

递归算法

本文为10个最经典递归实例让你秒懂递归算法的后5个：

递归算法的定义、详细讲解和5个初级练习见上篇文章：

递归算法练习

1.递归逆向输出字符串

题目要求：
使用递归算法逆向输出给定的字符串。
输入：abcd
输出：dcba

用Python逆序输出字符串其实非常简单，两行搞定：

a = input("输入字符串：")
print(a[::-1])

这里我们便于理解递归算法，还是老规矩，先自己做再看答案

def re(s, n):
    if n==0:
        return
    else:
        print(s[n-1],end="")
        return re(s,n-1)

a = input("输入字符串：")
re(a, len(a))

1) 先输出当前位
end = ""表示print输出当前字符后不换行；
2) 输出上一位，表达式： re(s,n-1)
3) 终止条件: n==0

2.兔子繁殖

题目要求：
一般兔子出生两个月后，就有繁殖的能力。
假设一对兔子从出生的两个月后每个月能生出一对兔子来，并且所有的兔子都不死，那么一年后有多少只兔子？

思路分析：

1）第1个月兔子还是1对；
2）第2个月，会有2对兔子（1对老兔子+1对新兔子）；
3）第3个月开始，会有3对兔子（老兔子1对 + 老兔子又生1对 + 1对小兔子）4）第4个月，会有5对兔子（老+老2月生+老3月生+老4月生+2月新兔子刚生的）

发现规律了吗？
初始: F0=1;
1月： F1=1;
2月： F2=2=F0+F1;
3月： F1=3=F1+F2；
4月： F1=5=F2+F3；
典型的斐波那契数列，代码如下：

def fib(n):
    if n<=1:
        return 1
    else:
        return fib(n-1)+fib(n-2)

a = int(input("输入月数："))
n=fib(a)
print("第%d个月共有%d只兔子出生"%(a,n))

3.走台阶

题目要求：
一个小学生在玩走台阶，可以一次走一个台阶，也可以一次走两个台阶。
请问有多少种走法？

思路分析：

有两种走法：
第一种走法：
第一次走了一个台阶，那么还剩下n-1个台阶还没走，剩下的n-1个台阶的走法有f(n-1)种。

第二种走法：
第一次走了两个台阶，那么还剩下n-2个台阶还没走，剩下的n-2个台阶的走法有f(n-2)种。

所以，全部走法就是这两种走法之和了，即 f(n) = f(n-1) + f(n-2)。

代码如下：

def f(n):
    if n<=1:
        return 1
    else:
        return f(n-1) + f(n-2)

a = int(input("请输入台阶数："))
n = f(a)
print("一共有%d种走法"%(n))

4. 求最大公约数

题目要求：
给定两个整数，求最大公约数。

'''
输入的两个数字 m=14，n=24
用求余数的方法，从第2次开始
m=n, n=m%n，
当余数为0时，最后的公约数为m
m  n  r
14 24 14
24 14 10
14 10 4
10 4  2
4  2  0
2  0
'''
def gcd(m,n):
    r = m%n
    m = n
    n = r
    if r==0:
        return m
    else:
        return gcd(m,n)

a = int(input("输入第一个整数："))
b = int(input("输入第二个整数："))
n=gcd(a,b)
print("%d 和 %d 的最大公约数为 %d"%(a,b,n))

5. 汉诺塔问题（难度进阶）

题目要求：
输入盘的总数，求从最左侧移到最右侧需要多少步。

这道题目的相比难度较大，挑战一下吧

def move(n, mfrom, mto):
    global i
    print("%d步：将%d号盘子从%s->%s"%(i,n,mfrom,mto))
    i += 1

def hanoi(n,A,B,C):
    if n==1:
        move(1,A,C)
    else:
        hanoi(n-1, A, C, B)
        move(n, A, C)
        hanoi(n-1, B, A, C)

i = 1
a = int(input("输入一个整数："))
hanoi(a,"A","B","C")