以上就是给各位分享为什么python中的递归这么慢？，其中也会对为什么python中的递归这么慢进行解释，同时本文还将给你拓展Python为什么这么慢？、Python中的递归、Python中的递归关系
以上就是给各位分享为什么python中的递归这么慢？，其中也会对为什么python中的递归这么慢进行解释，同时本文还将给你拓展Python 为什么这么慢？、Python中的递归、Python中的递归关系、python中的递归函数等相关知识，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
为什么python中的递归这么慢？（为什么python中的递归这么慢）
因此，我在闲逛时使用了递归，我发现使用递归的循环比常规的while循环要慢得多，我想知道是否有人知道为什么。我已经包括了我下面所做的测试：
>>> import timeit>>> setu="""def test(x): x=x-1 if x==0: return x else: test(x) """>>> setu2="""x=10while x>0: x=x-1""">>> timeit.timeit(stmt="test(10)",setup=setu,number=100)0.0006629826315997432>>> timeit.timeit(stmt=setu2,number=100)0.0002488750590750044>>> setu="""def test(x): x=x-1 if x==0: return x test(x) """>>> timeit.timeit(stmt="test(10)",setup=setu,number=100)0.0006419437090698921但是，在上一次测试中，我注意到如果删除该else语句，则表明速度略有提高，因此我想知道if语句是否是造成循环速度差异的原因？
答案1
小编典典您已将函数编写为尾递归。在许多命令式和函数式语言中，这将触发尾部递归消除，在这种情况下，编译器用简单的JUMP替换了CALL /
RETURN指令序列，从而使该过程与迭代大致相同，而与常规堆栈帧分配相反递归函数调用的开销。但是，Python不使用尾部递归消除，如以下一些链接所述：
http://neopythonic.blogspot.com/2009/04/tail-recursion-
elimination.html
http://metapython.blogspot.com/2010/11/tail-recursion-elimination-in-
python.html
从链接中可以看到，有一些默认情况下不存在的原因，并且您可以通过多种方式对其进行破解，但是默认情况下，Python会使用生成器函数之类的东西来创建复杂的指令序列，递归。
Python 为什么这么慢？
大家好，我是猫哥。今天分享一篇文章，讨论了拖慢 Python 整体性能的三大原因。在开始正文之前，需要说明一下（免得有人误以为 Python 慢就不值得使用）：性能很关键，但并不总是决定因素，语言的选择是系统性的问题，需要多方考虑。
本文讨论的三个原因，解释了 Python 性能的天花板在哪里，认识这几个方面，就有助于认识这门语言的特点，同时也是在寻找突破口：在什么层面上应该（should）、可以（can）、怎么（how）做出优化？
我前不久刚翻译的一篇文章《GIL 已经被杀死了么？》，据它介绍，GIL 不用太久将成为历史，这真是个好消息。
作者：laixintao | 转载：Python猫
（本文经原作者授权转载，不得二次转载）
原文： https://www.kawabangga.com/posts/2979
Python 在近几年变得异常流行，Python 语言学习成本低，写出来很像伪代码（甚至很像英语），可读性高，等等有很多显而易见的优点。被 DevOps, Data Science, Web Development 各种场景所青睐。但是这些美誉里面从来都没有速度。相比于其他语言，无论是 JIT 的，还是 AOT 的，Python 几乎总是最慢的。导致 Python 的性能问题的有很多方面，本文尝试谈论一下这个话题。
Python 有 GIL
Python 是一种“解释型”语言
Python 是动态类型的语言
GIL
现代计算机处理器一般都会有多核，甚至有些服务器有多个处理器。所以操作系统抽象出 Thread，可以在一个进程中 spawn 出多个 Thread，让这些 Thread 在多个核上面同时运行，发挥处理器的最大效率。（在 top 命令里面可以看到系统中的 threads 数量）
所以很显然，在编程时使用 Thread 来并行化运行可以提升速度。
但是 Python （有时候）不行。
Python 是不需要你手动管理内存的（C 语言就需要手动 malloc/free），它自带垃圾回收程序。意思是你可以随意申请、设置变量，Python 解释器会自动判断这个变量什么时候会用不到了（比如函数退出了，函数内部变量就不用到了），然后自动释放这部分内存。实现垃圾回收机制有很多种方法，Python 选择的是引用计数+分代回收。引用计数为主。原理是每一个对象都记住有多少其他对象引用了自己，当没有人引用自己的时候，就是垃圾了。
但是在多线程情况下，大家一起运行，引用计数多个线程一起操作，怎么保证不会发生线程不安全的事情呢？很显然多个线程操作同一个对象需要加锁。
这就是 GIL，只不过这个锁的粒度太大了，整个 Python 解释器全局只有一个 Thread 可以运行。详见 dabeaz 博客。
绿色表示正在运行的线程，一次只能有一个。
因为其他语言没有 GIL，所以很多人对 GIL 误解。比如：
“Python 一次只能运行一个线程，所以我写多线程程序是不需要加锁的。” 这是不对的，“一次只能运行一个线程”指的是 Python 解释器一次只能运行一个线程的字节码（Python 代码会编译成字节码给Python虚拟机运行），是 opcode 层面的。一行 Python 代码，比如 a += 1 ，实际上会编译出多条 opcode：先 load 参数 a，然后 a + 1，然后保存回参数 a。假如 load 完成还没计算，这时候线程切换了，其他线程修改了 a 的值，然后切换回来继续执行计算和存储 a，那么就会造成线程不安全。所以多线程同时操作一个变量的时候，依然需要加锁。
“Python 一次只能运行一个线程，所以 Python 的多线程是没有意义的。” 这么说也不完全对。假如你要用多线程利用多核的性能，那 Python 确实不行。但是假如 CPU 并不是瓶颈，网络是瓶颈，多线程依然是有用的。通常的编程模式是一个线程处理一个网络连接，虽然只有一个线程在运行，但其他线程都在等待网络连接，也不算“闲着”。简单说，CPU 密集型的任务，Python 的多线程确实没啥用（甚至因为多线程切换的开销还会比单线程慢），IO 密集型的任务，Python 的多线程依然可以加速。
这么说可能比较好理解：无论你的电脑的 CPU 有多少核，对 Python 来说，它只用 1 个核。
其他的 Python Runtime 呢？Pypi 有 GIL，但是可以比 CPython 快 3x。Jython 是基于 JVM 的，JVM 没有 GIL，所以 Jython 依然 JVM 的内存分配，它也没有 GIL。
其他语言呢？刚刚说了 JVM，Java 也是用的引用计数，但是它的的 GC 是 multithread-aware 的，实现上更复杂一些（有朋友跟我说 Java 已经不是引用计数了，这个地方请读者注意，附一个参考资料）。JavaScript 是单线程异步编程的模式，所以它没有这个问题。
作为一个解释型的语言……
像 C/C++/Rust 这些语言直接编译成机器码运行，是编译型语言；Python 的运行过程是虚拟机读入 Python 代码（文本），词法分析，编译成虚拟机认识的 opcode，然后虚拟机解释 opcode 执行。但这其实不是最主要的原因，Python import 之后会缓存编译后的 opcode，（pyc 文件或者 __pycache__ 文件夹）。所以读入、词法分析和编译并没有占用太多的时间。
那么真正的慢的是哪一步分呢？就是后面的虚拟机解释 opcode 执行的部分。前期的编译是将 Python 代码编译成解释器可以理解的中间代码，解释器再将中间代码翻译成 CPU 可以理解的指令。相比于 AOT（提前编译型语言，比如C）直接编译成机器码，肯定是慢的。
但是为什么 Java 不慢呢？
因为 Java 有 JIT。即时编译技术将代码分成 frames，AOT 编译器负责在运行时将中间代码翻译成 CPU 可以理解的代码。这一部分跟 Python 的解释器没有太大的区别，依然是翻译中间代码、执行。真正快的地方是，JIT 可以在运行时做优化，比如虚拟机发现一段代码在频繁执行（大多数情况下我们的程序都在反复执行一段代码），就会开始优化，将这段代码用更改的版本替换掉。这是仅有虚拟机语言才有的优势，因为要收集运行时信息。像 gcc 这种 AOT编译器，只能基于静态分析做一些分析。
为什么 Python 没有 JIT 呢？
第一是 JIT 开发成本比较高，非常复杂。C# 也有很好的 JIT，因为微软有钱。
第二是 JIT 启动速度慢，Java 和 C# 虚拟机启动很多。CPython 也很慢，Pypy 有 JIT，它比 CPython 还要慢 2x – 3x。长期运行的程序来说，启动慢一些没有什么，毕竟运行时间长了之后代码会变快，收益更高。但是 CPython 是通用目的的虚拟机，像命令行程序来说，启动速度慢体验就差很多了。
第三是 Java 和 C# 是静态类型的虚拟机，编译器可以做一些假设。（这么说不知道对不对，因为 Lua 也有很好的 JIT）
动态类型
静态类型的语言比如 C，Java，Go，需要在声明变量的时候带上类型。而 Python 就不用，Python 帮你决定一个变量是什么类型，并且可以随意改变。
动态类型为什么慢呢？每次检查类型和改变类型开销太大；如此动态的类型，难以优化。
动态类型带来好处是，写起来非常简单，符合直觉（维护就是另一回事了）；可以在运行时修改对象的行为，Monkey Patch 非常简单。
近几年的语言都是静态类型的，比如 Go，Rust。静态类型不仅对编译器来说更友好，对程序员来说程序也更好维护。个人认为，未来是属于静态类型的。
阅读资料：
Python 官方 wiki (https://wiki.python.org/moin/GlobalInterpreterLock)
Removing Python’s GIL: The Gilectomy
(https://www.youtube.com/watch?v=P3AyI_u66Bw)
David Beazley 有关 GIL 的 Slides：http://www.dabeaz.com/GIL/ ，视频（比较糊，毕竟2010年的）
Gilectomy的最新动态
(https://lwn.net/Articles/754577/)
https://hackernoon.com/why-is-python-so-slow-e5074b6fe55b
https://jakevdp.github.io/blog/2014/05/09/why-python-is-slow/
https://hacks.mozilla.org/2017/02/a-crash-course-in-just-in-time-jit-compilers/
随机推荐，偶遇精彩
1
GIL 已经被杀死了么？
2
听说苏州是互联网的荒漠，真的吗？
3
为什么Python不用设计模式？
4
你真的知道Python的字符串是什么吗？
本文分享自微信公众号 - Python猫（python_cat）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
Python中的递归
1、函数执行流程
(调用函数，保存当前的内容，压栈函数并创建栈帧。执行里面的语句）
全局帧中生成foo1、foo2、foo3、main的函数对象。(栈，先进后出，后进先出）。
main函数调用
main 中查找内建函数print压栈，将常量字符串压栈，调用函数，弹出栈顶。
main中全局函数foo1压栈，将常量100,101压栈，调用函数foo1，创建栈帧。Print函数压栈，字符串和变量b、b1压栈，调用函数，弹出栈帧，返回值。
Main中全局查找foo2函数压栈，将常量200压栈，调用foo2，创建栈帧。foo3函数压栈，变量c引用压栈，调用foo3，创建栈帧。foo3完成print函数调用后返回。foo2回复调用，执行print后，返回值。Main中foo2调用结束弹出栈顶，main函数继续执行print函数调用，弹出栈顶，main函数返回。
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='' '')
def fib(n):
return 1 if n<2 else fib(n-1)+fib(n-2)
for i in range(5):
print(fib(i),end='' '')3、递归要求
递归一定要有退出条件，递归调用一定要执行到这个退出条件，没有退出条件的递归调用，就是无限调用。
递归调用的深度不宜过深。
Python中对递归调用的深度做了限制，以保护解释器。
超过递归调用深度，会抛出异常的。
4、递归的性能
循环稍微复杂一些，但是只要不是死循环，可以多次迭代直至算到结果。
改进。左边的fib函数和循环的思想类似。
参数n是边界条件，用n来计数。
上一次的计算结果作为下一次结果的实参。
import datetime
n=35
start = datetime.datetime.now()
def fib(n):
return 1 if n<2 else fib(n-1)+fib(n-1)
for i in range(n):
print(fib(i),end='''')
delta = (datetime.datetime.now()-start).total_seconds()
print(delta)效率比较低。
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)
print(fib(5))#斐波那契数列改进方式
左边的fib函数和循环的思想类似
参数n是边界条件，用n来计数。
上一次的计算结果作为函数的实参。
效率很高
和循环相比，性能相近，所以说递归效率不一定很低。但是深度有限。
5、间接递归
def foo1（）：
foo2（）
def foo2（）：
f1oo（）
foo1（）
是通过别的函数调用了函数本身。
但是，如果构成了循环递归调用时非常危险。
6、递归总结
是一种很自然的表达，符合逻辑思维。
相对运行效率较低，每次调用函数都要开辟栈帧
递归有深度限制，如果递归层次太深，函数反复压栈，栈内存很快就溢出了。
如果有限次数的递归，可以使用递归调用，或者使用循环替代，循环代码稍微复杂,但是只要不是死循环，可以多次迭代直至算出结果。
绝大多数递归，都可以使用循环实现。
即使代码很简单，但是能不用则不用递归。
Python中的递归关系
import math
def printRecurrence():
x = [0]*51 #initialize list of x values
x[0] = 1
x[1] = 1/3
for i in range(1,51):
x[i+1] = (13/3)*x[i] - (4/3)*x[i-1]
print(x[i])
我收到的输出是：
0.3333333333333333 0.11111111111111094 0.03703703703703626 0.012345679012342514 0.004115226337435884 0.0013717421124321456 0.00045724737062478524 0.00015241578946454185 5.0805260179967644e-05 1.6935074827137338e-05 5.644977344304949e-06 1.8814687224716613e-06 6.263946716372672e-07 2.0575194713260943e-07 5.63988753916179e-08 -2.994080281313502e-08 -2.049419793790756e-07 -8.481608402251475e-07 -3.402107668470205e-06 -1.361158544307069e-05 -5.444739336201271e-05 -0.00021778992397796082 -0.0008711598127551465 -0.0034846392899683535 -0.013938557172856001 -0.05575422869575153 -0.22301691478444863 -0.8920676591382753 -3.5682706365532617 -14.2730825462131 -57.092330184852415 -228.36932073940963 -913.4772829576384 -3653.909131830553 -14615.63652732221 -58462.546109288836 -233850.18443715532 -935400.7377486213 -3741602.950994485 -14966411.80397794 -59865647.21591176 -239462588.86364704 -957850355.4545882 -3831401421.8183527 -15325605687.27341 -61302422749.09364 -245209690996.37457 -980838763985.4983 -3923355055941.993
这只适用于前13个打印值.我提供的证据是xn = 3-n,这在很大程度上与我的脚本的值不匹配.我在计算中做错了吗？我一直无法看到它.
解决方法
Jean-François关于浮点累积误差的观点是正确的.但是,分数模块似乎无法将多个Fraction对象相乘,因此必须在fraction对象中声明所有数值.感谢他为这个问题使用正确的模块.
确切的答案
import math
import fractions
def printRecurrence():
x = [0]*51 #initialize list of x values
x[0] = fractions.Fraction(1,1)
x[1] = fractions.Fraction(1,3)
for i in range(1,50):
x[i+1] = fractions.Fraction(13*x[i]/3) - fractions.Fraction(4*x[i-1]/3)
print(float(x[i+1]),3**(-(i+1)),x[i+1]-(3)**(-(i+1)))
printRecurrence()
打印输出显示计算与证明答案完全匹配.
不精确但有启发性的答案
十进制模块允许自定义级别的精度;要达到50次迭代,需要60点或更高的精度.
import math
from decimal import *
getcontext().prec = 60
def printRecurrence():
x = [0]*51 #initialize list of x values
x[0] = Decimal(1)
x[1] = Decimal(1)/Decimal(3)
for i in range(1,50):
x[i+1] = (Decimal(13)/Decimal(3))*x[i] - (Decimal(4)/Decimal(3))*x[i-1]
print(float(x[i+1]),float(x[i+1]-Decimal(3)**(-(i+1))))
printRecurrence()
和Jean-François的答案一样,我打印了结果,计算出的值为3 ** – n和差异.可以使用精度级别getcontext().prec来查看对结果的影响.
0.111111111111 0.111111111111 -1e-60 0.037037037037 0.037037037037 -4e-60 0.0123456790123 0.0123456790123 -1.57e-59 0.00411522633745 0.00411522633745 -6.243e-59 0.00137174211248 0.00137174211248 -2.4961e-58 0.000457247370828 0.000457247370828 -9.984e-58 0.000152415790276 0.000152415790276 -3.993577e-57 5.08052634253e-05 5.08052634253e-05 -1.59742978e-56 1.69350878084e-05 1.69350878084e-05 -6.38971879e-56 5.64502926948e-06 5.64502926948e-06 -2.5558875048e-55 1.88167642316e-06 1.88167642316e-06 -1.02235500146e-54 6.27225474386e-07 6.27225474386e-07 -4.08942000567e-54 2.09075158129e-07 2.09075158129e-07 -1.63576800226e-53 6.96917193763e-08 6.96917193763e-08 -6.54307200905e-53 2.32305731254e-08 2.32305731254e-08 -2.61722880362e-52 7.74352437514e-09 7.74352437514e-09 -1.04689152145e-51 2.58117479171e-09 2.58117479171e-09 -4.18756608579e-51 8.60391597238e-10 8.60391597238e-10 -1.67502643432e-50 2.86797199079e-10 2.86797199079e-10 -6.70010573727e-50 9.55990663597e-11 9.55990663597e-11 -2.68004229491e-49 3.18663554532e-11 3.18663554532e-11 -1.07201691796e-48 1.06221184844e-11 1.06221184844e-11 -4.28806767185e-48 3.54070616147e-12 3.54070616147e-12 -1.71522706874e-47 1.18023538716e-12 1.18023538716e-12 -6.86090827496e-47 3.93411795719e-13 3.93411795719e-13 -2.74436330998e-46 1.3113726524e-13 1.3113726524e-13 -1.09774532399e-45 4.37124217466e-14 4.37124217466e-14 -4.39098129597e-45 1.45708072489e-14 1.45708072489e-14 -1.75639251839e-44 4.85693574962e-15 4.85693574962e-15 -7.02557007356e-44 1.61897858321e-15 1.61897858321e-15 -2.81022802942e-43 5.39659527735e-16 5.39659527735e-16 -1.12409121177e-42 1.79886509245e-16 1.79886509245e-16 -4.49636484708e-42 5.99621697484e-17 5.99621697484e-17 -1.79854593883e-41 1.99873899161e-17 1.99873899161e-17 -7.19418375532e-41 6.66246330538e-18 6.66246330538e-18 -2.87767350213e-40 2.22082110179e-18 2.22082110179e-18 -1.15106940085e-39 7.40273700597e-19 7.40273700597e-19 -4.60427760341e-39 2.46757900199e-19 2.46757900199e-19 -1.84171104136e-38 8.22526333997e-20 8.22526333997e-20 -7.36684416545e-38 2.74175444666e-20 2.74175444666e-20 -2.94673766618e-37 9.13918148886e-21 9.13918148886e-21 -1.17869506647e-36 3.04639382962e-21 3.04639382962e-21 -4.71478026589e-36 1.01546460987e-21 1.01546460987e-21 -1.88591210636e-35 3.38488203291e-22 3.38488203291e-22 -7.54364842542e-35 1.12829401097e-22 1.12829401097e-22 -3.01745937017e-34 3.76098003645e-23 3.76098003657e-23 -1.20698374807e-33 1.25366001171e-23 1.25366001219e-23 -4.82793499227e-33 4.17886668798e-24 4.1788667073e-24 -1.93117399691e-32 1.39295549185e-24 1.3929555691e-24 -7.72469598763e-32
python中的递归函数
递归的定义：
在函数内部直接或者间接调用函数本身
递归的应用：
△求一个数的阶乘
1 def jiecheng(n):
2 if n == 1:
3 return 1
4 else:
5 return n*jiecheng(n-1)
6 print(jiecheng(4))△求第几个斐波那契数
1 def f(n):
2 if n == 2:
3 return 1
4 elif n ==1:
5 return 1
6 else:
7 return f(n-1)+f(n-2)
8 print(f(33))△二分法查找
1 l = [1,3,5,6,11,13,15,17,21,32,36,52,56,58,66,77,88,99]
2 def find(l,n,start=0,end=None):
3 end = len(l) if end is None else end
4 mid_index = (end-start)//2 + start
5 if start>=end:
6 return ''找不到''
7 else:
8 if n>l[mid_index]:
9 return find(l,n,mid_index+1,end)
10 elif n<l[mid_index]:
11 return find(l,n,start,mid_index-1)
12 else:return mid_index
13
14 res = find(l,17)
15 print(res)
我们今天的关于为什么python中的递归这么慢？和为什么python中的递归这么慢的分享已经告一段落，感谢您的关注，如果您想了解更多关于Python 为什么这么慢？、Python中的递归、Python中的递归关系、python中的递归函数的相关信息，请在本站查询。
本文标签：
