递归函数及应用

函数在运行过程中 直接或间接地调用了自身.

def index():
    print('from index')
    index()
index()

def index():
    print('from index')
    func()

def func():
    print('from func')
    index()
index()

可以看到在pycharm中,递归函数并非可以无限次递归.

我们来统计一下index函数反复调用的次数

count = 1
def index():
    print('from index')
    global count
    count += 1
    print(count)
    index()
index()

因为Pycharm有自身的应急机制,官网原则上默认最大递归深度为1000次.(通常为997/998次)

import sys
print(sys.getrecursionlimit())  # 1000

事实上,我们可以更改递归的次数

import sys
print(sys.setrecursionlimit(2000))

from index
1998
from indexTraceback (most recent call last):
  File "C:/me/JetBrains/pythonProject/递归函数/递归函数.py", line 11, in index
    index()
 
RecursionError: maximum recursion depth exceeded while calling a Python object

递归的本质:

        递推: 一层层往下推理.

        回溯:根据最后的结果往前推导.

递归函数并非无限循环的过程,其有两个特点:

1.每次递归,复杂度必须降低.

2.一定要有明确的结束条件.

使用场景:

1: 有5个同心圆,最小的圆半径为3cm,从内而外每个外圆的半径都比内圆多2cm,求最每个圆的半径.

推理过程:

        第一个圆半径为3, 其外层圆为3+2,

        第二个圆半径为3+2, 其外层圆为3+2+2,

        ......

封装为函数

def r(n):
    if n == 1:
        return 3
    return r(n-1) + 2
print(r(5))   # 11

2: 从列表中提取出数字

l1 = [1,[2,[3,[4,[5,[6,[7,[8,[9,]]]]]]]]]
def get_num(l1):
    for i in l1:
        if isinstance(i,int):
            print(i)
        else:
            get_num(i)
get_num(l1)

# 1
# 2
# 3
# 4
# 5
# 6
# 7
# 8
# 9