函数的递归调用

一 函数的递归调用

函数的递归调用：是函数嵌套调用的一种特殊形式

函数的递归本质是：重复执行代码

具体是指：

? 在调用一个函数的过程中又直接或间接的调用本身

直接调用本身

def f1():
  	print(‘QAQ‘)
    f1()

f1()

间接调用本身

def f1():
  	print(‘---->f1‘)
    f2()
   
def f2():
  	print(‘---->f2‘)
    f1()
    
f1()

二 代码的循环运行方式

一段代码的循环运行的方案有两种

方式一：while 、for 循环

while True:
  	print(111)
    print(222)
    print(333)
    

方式二：递归的本质就是循环

def f1():
  	print(123)
    print(234)
    f1()
    
f1()

需要强调的一点是：

? 递归不应该无限的调用下去，必须在某种情况下结束递归

n = 0
while n < 10:
  	n += 1
    

函数递归方式

def f1(n):
  	if n == 10:
      	break
    print(n)
    n += 1
		f1(n)
 
f1(0)

三 递归的两个阶段

回溯：一层一层调用下去

递推：满足某种结束条件，结束递归调用，然后一层一层返回

示例：

age(5) = age(4) + 10
age(4) = age(3) + 10
age(3) = age(2) + 10
age(2) = age(1) + 10
age(1) = 18

递归：

def age(n):
		if n == 1:
    return 18
  	return age(n-1) + 10
  
age(5)#58

具体案例：

? 某公司四个员工坐在一起，问第四个人薪水，他说比第三个人多1000，问第三个人薪水，第他说比第二个人多1000，问第二个人薪水，他说比第一个人多1000，最后第一人说自己每月5000，请问第四个人的薪水是多少？

解题思路：

? 如果想要知道第四个人的薪水，那么就需要知道第三个人的 ，而第三个人的取决第二个人的，第二个人的薪水又取决第一个人的，所以数学表达式为：

salary(4) = salary(3) + 1000
salary(3) = salary(2) + 1000
salary(2) = salary(1) + 1000
sa1ary(1) = 5000

即：
salary(n) = salary(n-1)+ 1000
sa1ary(1) = 5000

递归代码：

def salary(n):
		if n == 1:
				return 5000
    return salary(n-1) + 1000
  
res = salary(4)
print(res) #8000

程序分析：

? 在为满足 n == 1 时，一一直回溯，当 n == 1 时拿到对应的值并结束回溯，从而进入递推阶段，依次推导得到最终的结果。

四 递归的应用

递归的本质技术在做重复的事情，所以理论上递归可以解决的问题，循坏也都可以解决，只不过在某些情况下，使用递归会跟容易实现，比如一个桥套多层的列表，要求打印列表内所有的元素，那么使用递推就比较容易。

具体案例：

l=[1,2,[3,[4,[5,[6,[7,[8,[9,10,11,[12,[13,]]]]]]]]]]

def f1(list1):
    for line in list1:
        if type(line) is list:
            #如果是列表，应该在循环，再判断即重新运行本身的代码
            f1(line)
        else:
            print(line, end=‘ ‘) #1 2 3 4 5 6 7 8 9 10 11 12 13 

f1(l)

使用递归，只需要分析重复执行的代码逻辑，以及进入下一次递归调用的条件和递归结束的条件即可，代码实现比较简洁清晰。

函数的递归调用

原文：https://www.cnblogs.com/xy-han/p/12567211.html