Python递归讲解

引入

递归是一种常见的解决问题的方法，即把问题逐渐简单化。
递归的基本思想就是“自己调自己”，利用了计算机的强大计算能力。
利用递归可以用简单的程序来解决一些复杂的问题。比如：斐波那契数列的计算、汉诺塔等问题。

分析

递归机构包括两部分：

  • 定义递归头。解答：什么时候不调用自身方法。如果没有头，将陷入死循环，也就是递归结束的条件。

  • 递归体。解答：什么时候需要调用自身方法。

示例：

使用递归求n！

1
2
3
4
5
6
def factorial(n):
    if n == 1:
        return n 
    else:
        return n*factorial(n-1)# 递归
print(factorial(5))

示例题

斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……。
在数学上，费波那契数列是以递归的方法来定义：
F0 = 0 (n=0)
F1 = 1 (n=1)
Fn = F[n-1]+ Fn-2
方法一：循环

1
2
3
4
5
6
7
8
9
10
11
12
13
def feib1(n):
    fbList = []
    if n == 0:
        fbList.append(0)
    elif n == 1:
        fbList.append(0)
        fbList.append(1)
    else:
        fbList = [0,1]
        for i in range(2,n+1):
            fbList.append(fbList[i-1]+fbList[i-2])
    return fbList
print(feib1(10))

1
2
3
4
5
6
7
8
#方法二：递归
def feib2(n):
    if n==0:
        return 0
    elif n==1 or n==2:
        return 1
    return feib2(n-1)+feib2(n-2)
print(feib2(10))

练习

没有练习

关于

本篇文章的作者是Minecraft-Sep