Python递归函数

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Python递归函数，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7668字，纯文字阅读大概需要11分钟。

内容图文

函数执行流程

要明白递归首先需要明白函数的执行流程。

比如下面的这段程序。

def foo1(b, b1=3):
    print("foo1 called", b, b1)

def foo2(c):
    foo3(c)
    print("foo2 called", c)

def foo3(d):
    print("foo3 called", d)
def main():
    print("main called")
    foo1(100, 101)
    foo2(200)
    print("main ending")

main()

结果为：
main called
foo1 called 100 101
foo3 called 200
foo2 called 200
main ending

上面的代码执行流程为：

首先在全局帧中生成foo1、foo2、foo3、main函数对象。
然后main函数调用。
main函数中查找内建函数print压栈，然后将常量字符串压栈，然后调用函数，弹出栈顶。
main函数中全局查找函数foo1压栈，然后将常量100,101压栈，调用函数foo1，创建栈帧。然后字符串和变量b,b1压栈，调用函数，弹出栈顶，返回值。
main函数中全局查找函数foo2函数压栈，然后将常量200压栈，调用foo2，创建栈帧。foo3函数压栈，变量c引用压栈，调用foo3，创建栈帧。foo3完成print函数调用后返回。foo2恢复调用，执行print后，返回值。main中foo2调用结束弹出栈顶，main继续执行print函数调用，弹出栈顶，main函数返回。

递归

所谓的递归也就是函数直接或者间接调用自身。需要注意的是递归一定要有边界条件（不然就就是死循环），递归前进段、递归返回段，当边界条件不满足的时候，递归前进，而当递归条件满足的时候，递归返回。

递归相比于循环，只是让解决方案更加清晰，并没有性能上的优势。在有些情况下，如果使用循环，程序的性能可能会更高，而如果使用递归的话，程序可能更容易理解。

比如要生成一个斐波拉契数列，1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... ?如果设f(n)为该数列的第n项，那么可以推导出这样的公式：f(n)=f(n-1)+f(n-2).

使用循环，生成斐波拉契数列，代码为：

pre = 0
cur = 1#第一个
print(pre,cur,end=" ")
n = 4
for i in range(n-1):
    pre,cur = cur,pre+cur
    print(cur,end = " ")

结果为：

0 1 1 2 3 

将它抽象出函数：

def fib(n):
    pre = 0
    cur = 1
    print(cur,end=" ")
    for i in range(n-1):
        pre,cur = cur,pre+cur
        print(cur,end = " ")
fib(10)

结果为：

1 1 2 3 5 8 13 21 34 55

而如果使用递归的话，代码可以很简洁：

#第n项的数字为：

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

上面的代码可以简化为：
def fib(n):
    return 1 if n<2 else fib(n-1)+fib(n-2)
fib(10)

而生成数列的代码为：

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

print(fib(10))

for i in range(11):
    print(fib(i), end=' ')

结果为：
89
1 1 2 3 5 8 13 21 34 55 89

由上面的例子可以看到，递归一定要有退出条件，而递归调用一定会执行到这个退出条件，如果没有退出条件的递归调用，就是无限调用，会陷入无限循环，而且递归调用的深度不宜过深，Python对递归调用的深度做了限制（1000）以保护解释器，超过递归深度的限制，会抛出recursionerror错误，同时可以使用sys.getrecursionlimil()设置递归的深度。

递归的性能

循环稍微复杂一些，但是只要不是死循环，就可以多次迭代算出结果，递归函数的代码极简易懂，但是只能获取到最外层的函数调用，内部的递归结果都是中间结果，而且给定一个N都要进行近2N次递归，深度越深，效率就会越低，为了获取斐波拉契数列需要再在外面套一个n的循环，效率就更低了。如果递归复杂，函数会反复的压栈，这样栈的内存很快就会溢出。所以会有递归深度限制。如下面的代码：

import datetime
start = datetime.datetime.now()
pre = 0
cur = 1 # No1
print(pre, cur, end=' ')
n = 35
for i in range(n-1):
    pre, cur = cur, pre + cur
    print(cur, end=' ')
    delta = (datetime.datetime.now() -start).total_seconds()

print(delta)

结果为：

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 0.001

import datetime
n = 35
start = datetime.datetime.now()
def fib(n):
    return 1 if n < 2 else fib(n-1) + fib(n-2)
for i in range(n):
    print(fib(i), end=' ')
    delta = (datetime.datetime.now() - start).total_seconds()
print(delta)

结果为：

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 9.371536

上面的例子可以看到for循环，只需要0.01秒就可以很快算出35个斐波拉契数列，而递归的话则需要9秒多。效率特别低，这个时候有什么可以改进的吗？

pre = 0
cur = 1#第一个
print(pre,cur,end=" ")
def fib(n,pre = 0,cur = 1):
    pre,cur = cur,pre+cur
    print(cur,end=" ")
    if n ==2:
        return
    fib(n-1,pre,cur)
    
fib(10)

结果为：

0 1 1 2 3 5 8 13 21 34 55

上面的这个递归函数就和循环的思想很类似了，参数n是边界条件，用n来计数，上一次的计算结果直接用作函数的实参，这样的话，效率更高，和循环相比较的话，性能更近。

所以递归并不一样都是效率低下，但是它有深度限制。

可以对比下三个斐波拉契数列生成函数的效率。如下：

import datetime
# Fib Seq
start = datetime.datetime.now()
pre = 0
cur = 1 # No1
print(pre, cur, end=' ')
n = 35
# loop
for i in range(n-1):
    pre, cur = cur, pre + cur
    print(cur, end=' ')
delta = (datetime.datetime.now() - start).total_seconds()
print(delta)


# Fib Seq
start = datetime.datetime.now()
pre = 0
cur = 1 # No1
print(pre, cur, end=' ')
# recursion
def fib1(n, pre=0,cur=1):
    pre, cur = cur, pre + cur
    print(cur, end=' ')
    if n == 2:
        return
    fib1(n-1, pre, cur)

fib1(35)
delta = (datetime.datetime.now() - start).total_seconds()
print(delta)


start = datetime.datetime.now()
def fib2(n):
    if n < 2:
        return 1
    return fib2(n-1) + fib2(n-2)

for i in range(n):
    print(fib2(i), end=' ')
delta = (datetime.datetime.now() - start).total_seconds()
print(delta)

前面两个性能相当，而第三个效率特特别低下。写递归应该尽量避免写成第三个这样的。

间接递归

所谓的间接递归，就是通过别的函数间接调用了函数自身，但是，如果构成了循环递归调用就是件非常危险的事情，而且这种情况在代码复杂的情况下，很还可能发生。所以一定要规范代码，来避免发生这种调用的发生。比如下面这个例子。

def foo1():
    foo2()
def foo2():
    foo1()
foo1()

上面的代码就会陷入死循环。应该尽量的避免。

递归总结：

递归是一种很自然的表达，符合逻辑思维。
递归相对来讲运行效率低，每一次调用函数都要开辟栈帧。
递归有深度限制，如果递归的层次太深，函数反复的压栈，栈内存很快就会溢出。
如果是有限次的递归，可以使用递归调用，或者使用循环代码，循环代码稍微复杂一些，但是只要不是死循环，可以多次迭代直至算出结果。
绝大多数递归，都可以使用循环来实现。
即便递归代码简洁，但是能不用则不用递归。

练习题：

求n的阶乘！
将一个数逆序放入列表中，比如1234--[4,3,2,1]
解决猴子吃桃问题：猴子第一天摘下若干个桃子，马上吃了一半，还不过瘾，又多吃了一个，第二天早上又将剩下的桃子吃掉了一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想吃的时候，只剩下一个桃子，求第一天共摘了多少个桃子。

#求阶乘
def fac(n):#性能最好
    if n==1:
        return 1
    else:
        return n*fac(n-1)
fac(10)

结果为：

3628800

def fac1(n,p=1):
    if n==1:
        return p
    p*= n
    print(p)
    fac1(n-1,p)
    return p

fac1(10)

结果为：

10
90
720
5040
30240
151200
604800
1814400
3628800
10

def fac2(n,p=None):
    if p is None:
        p = [1]
    if n == 1:
        return p[0]
    p[0]*=n
    #print(p[0])
    fac2(n-1,p)
    return p[0]
fac2(10)

结果为：
3628800

def fac3(n,p=1):
    p*=n
    if n==1:
        return p
    else:
        return fac4(n-1,p)

fac3(10)

结果为：
3628800

2.将一个数逆序放入列表中

data = str(1234)

def revert(x):
    if x==-1:
        return " "
    return data[x]+revert(x-1)

print(revert(len(data)-1))

结果为：
4321 

def revert1(n,lst = None):
    if lst is None:
        lst = []
        
    lst.append(n%10)
    if n//10 ==0:
        return lst
    return revert1(n//10,lst)
revert1(12345)

结果为：

[5, 4, 3, 2, 1]

def revert2(n,lst = None):
    if lst is None:
        lst = []
        
    x,y=divmod(n,10)
    lst.append(y)
    if x==0:
        return lst
    return revert2(x,lst)

revert2(12345)

结果为：
[5, 4, 3, 2, 1]

num = 12354

def revert3(num,target=[]):
    if num:
        target.append(num[len(num)-1])#target.append(num[-1:])
        revert3(num[:len(num)-1])
    return target
print(revert3(str(num)))

结果为：
['4', '5', '3', '2', '1']

猴子吃桃问题：

def peach(day= 9,sum = 1):
    sum=2*(sum+1)
    day-=1
    if day ==0:
        return sum
    return peach(day,sum)
print(peach())

结果为：
1534

def monkey(n):
    if n==1:
        return 1
    return 2*monkey(n-1)+2
monkey(10)

结果为：
1534

这个猴子吃桃的问题，可以假设猴子摘了x个桃子

d1: x//2-1

d2:d1//2-1

d3:d2//2-1

……

d9:d8//2-1

d10:1

那么：

def peach(day = 10):if day==1:
        return 1
    return (peach(day-1)+1)*2
print(peach())

结果为：
1534

应该注意的是，这里必须是10，因为return (peach(day-1)+1)*2立即拿不到结果，必须通过再一次进入函数时判断是不是到了最后一天。也就是当前使用的值是由下一次函数调用得到的，所以要执行10次函数调用。换一种方式表达：

def peach(days = 1):
    if days==10:
        return 1
    return (peach(days+1)+1)*2
print(peach())

结果为：
1534

内容总结

以上是互联网集市为您收集整理的Python递归函数全部内容，希望文章能够帮你解决Python递归函数所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/688467.html

来源：【匿名】

【上一篇】python学习10—迭代器【下一篇】浅谈PHP运行Python脚本的方法

更多 ►

【Python递归函数】教程文章相关的互联网学习教程文章

思路：1. 使用列表保存结果；2. 使用栈（列表实现）存储结点；3. 当根结点存在，保存结果，根结点入栈；4. 将根结点指向左子树；5. 根结点不存在，栈顶元素出栈，并将根结点指向栈顶元素的右子树；6. 重复步骤3-6，直到栈空。LeetCode: 144. Binary Tree Preorder Traversal# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# ...

Python学习笔记__2.4章递归函数

# 这是学习廖雪峰老师python教程的学习笔记在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。使用递归函数写一个阶乘函数：def fact(n): if n==1: return 1 return n * fact(n - 1)计算过程：===> fact(5)===>5 * fact(4)===>5 * (4 * fact(3))===>5 * (4 * (3 * fact(2)))===>5 * (4 * (3 * (2 * fact(1))))===>5 * (4 * (3 * (2 * 1)))===>5 * (4 * (3 * 2))===>5 * (4 * ...

Python 第五天递归，计算器（2）【代码】

利用函数编写如下数列：斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，463681def func(arg1,arg2):if arg1 == 0:passarg3 = arg1 + arg2if arg3>1000;return arg3#他的调用者应该是他的前一次func函数，return func(arg2,arg3)result = func(0,1) print result 递归的返回值基于递归和正则表达式实现的计算器，源码...

python学习第37天GIL锁、死锁现象与递归锁、信号量、Event时间、线程queue【代码】【图】

一、GIL锁1. 什么是GIL全局解释器锁定义： In CPython, the global interpreter lock, or GIL, is a mutex that prevents multiple native threads from executing Python bytecodes at once. This lockis necessary mainly because CPython’s memory management is not thread-safe. (However, since the GIL exists, other features have grown to depend on the guarantees that it enforces.) ‘‘‘ 结论：在Cpython解释器...

python的递归【代码】【图】

今天，我们要讲的内容是关于python的递归。什么是递归？看这个名字，你也许能够猜出个大概。关于递归，我们有一个很经典的应用，就是我们以前高中一些数学题目中的累乘，像n *（n-1）* (n-2) * ... * 1。在这里，如果要让你计算最终的结果，你可能会想到用for循环来实现，但是，我们在这里可以稍微进行优化一下，比如像这个例子一样：#for循环def LSF(n):result = nfor i in range(1,n):result *= ireturn result#递归def LSF(n)i...

python 生成list的所有的子集（不使用递归且不引入标准库）【代码】

不使用递归且不引入标准库，单纯用两个for循环即可得出一个list的所有子集L = [1, 2, 3, 4]List = [[]]for i in range(len(L)): # 定长 for j in range(len(List)): # 变长 sub_List = List[j] + [L[i]] if sub_List not in L: List.append(sub_List)print(‘List =‘, List)主要思想：变长的 List 中的所有元素将会被不断地重复遍历，直到遍历完定长的 L 当然，不进行条件判断也行：L = [1...

python函数、递归、json模块操作【代码】

一、修改文件修改文件方法：简单粗暴直接，步骤以下：#1、打开一个文件，获取到文件的内容#2、对内容进行修改#3、清空文件的内容#4、把新的内容写入到文件代码示例：f=open(‘username‘,‘a+‘)f.seek(0)all_str=f.read()new_str=all_str.replace(‘123456‘,‘79910‘)f.seek(0)f.truncate()f.write(new_str)f.close() #把每行的内容加上str，代码示例：f=open(‘username‘,‘a+‘)f.seek(0)all_str=‘‘for s in f:new_s=‘syz...

python--递归（Recursion）【代码】

# while 1: # print(‘从前有座山‘)# 递归：在函数中调用自身函数 # def story(): # print(‘从前有座山‘) # story() # story()# RecursionError: maximum recursion depth exceeded while calling a Python object # 递归的错误，超过了递归的最大深度 # 最大递归深度默认为 997/998 ————是python从内存角度出发做出的限制# import sys # sys.setrecursionlimit(10000) # n = 0 # def story(): # global n...

python Day3 集合文件处理函数字符编码递归高级函数【代码】【图】

集合集合是一个无序的，不重复的数据组合，它的主要作用如下：去重，把一个列表变成集合，就自动去重了关系测试，测试两组数据之前的交集、差集、并集等关系常用操作s = set([3,5,9,10]) #创建一个数值集合 t = set("Hello") #创建一个唯一字符的集合 a = t | s # t 和 s的并集 b = t & s # t 和 s的交集 c = t – s # 求差集（项在t中，但不在s中） d = t ^ s ...

python3实现二叉树的遍历与递归算法解析【代码】【图】

1、二叉树的三种遍历方式二叉树有三种遍历方式：先序遍历，中序遍历，后续遍历即：先中后指的是访问根节点的顺序 eg:先序根左右中序左根右后序左右根　　遍历总体思路：将树分成最小的子树，然后按照顺序输出　　1.1 先序遍历　　　　a 先访问根节点　　　　b 访问左节点　　　　c 访问右节点　　　　a（b ( d ( h ) )( e ( i ) )）( c ( f )( g )) -- abdheicfg 　　1.2 中序遍历　...

python中递归函数【代码】

递归函数即直接或间接地调用自身以进行循环的函数 def mySum(L): if not L: return 0 else: return L[0]+mySum(L[1:])print mySum([1,2,3,4,5])这个函数用递归的方法计算列表所有元素的和在每一层，函数都递归的调用自己来计算列表剩余的值的和。还有一个递归方法计算阶乘：def factorial(n): if n==0 or n==1: return 1 else: return factorial(n-1) * nprint (factorial(5)) 12...

二叉树遍历（非递归版）——python【代码】

二叉树的遍历分为广度优先遍历和深度优先遍历广度优先遍历(breadth first traversal)：又称层次遍历，从树的根节点(root)开始，从上到下从从左到右遍历整个树的节点。深度优先遍历(depth first traversal)：对于一颗二叉树，深度优先遍历是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。深度优先遍历有重要的三种方法。这三种方式常被用于访问树的节点，它们之间的不同在于访问每个节点的次序不同。这三种遍历分别叫做先序遍...

Python 实现二分查找（递归版）【代码】

二分查找为什么使用二分查找： python中的列表，一般取值为遍历这个列表，直到取到你想要的值，但是如果你的列表是一个有着百万元素的列表呢，那样for循环遍历列表就会很慢，可能会循环几十万次，才能找到你需要的对应的值，那样不是很浪费资源嘛，所以为了更加快速的找到对应的值以及节省系统的资源，就有人发明了这种二分算法。原理:注意：二分查找必须是一个有序的列表，递增或递减都可以，但必须是一个有序列表. 二分查找也叫折...