递归的概念

我调用我自己，容易遇到递归最大深度的问题

修改递归深度的代码

import sys
sys.setrecursionlimit(1024)

示例代码

def tell_story():
    print("从前山上有座庙")
    print("庙里有个小和尚")
    print("庙里还有一个老和尚")
    print("老和尚在给小和尚讲故事")
    print("老和尚讲的故事是……")
    tell_story()
tell_story()

递归最重要的是出口条件

利用条件语句if来控制递归次数

注意函数内部使用外部变量，必须先声明全局变量

count = 0
def tell_story():
    global count
    count += 1
    print("从前山上有座庙")
    print("庙里有个小和尚")
    print("庙里还有一个老和尚")
    print("老和尚在给小和尚讲故事")
    print("老和尚讲的故事是……")
    if count < 5:
        print("这是第{}次".format(count))
        tell_story()
tell_story()

递归的例子

计算前n项和, 通过观察可以发现,每两个数字相加,都是在前一个数字的基础上加一,所以将n项之和转化为两项之和;

由于计算有极限,但是我们不知道最后一项的值,但是我们知道第一项的值,所以从后往前运算,可以得出结果,运算的起止条件就设为n等于0;

import sys
sys.setrecursionlimit(2048)
count = 0
def tell_story():
    global count
    count += 1
    print("从前山上有座庙")
    print("庙里有个小和尚")
    print("庙里还有一个老和尚")
    print("老和尚在给小和尚讲故事")
    print("老和尚讲的故事是……")
    if count < 5:
        print("这是第{}次".format(count))
        tell_story()
tell_story()
def get_sum(n):
    if n == 0:
        return 0
    return n + get_sum(n - 1)
print(get_sum(10))

补充 —- 斐波那契数列

斐波那契数列和求前n项和有一个共同特点,就是最前面的元素,比如在前n项和中,第一项为零,在斐波那契数列中,第一项和第二项的值都为1,可以把这种运算看作是因式分解,最后将一个很大的数字转换为多个基数求和;