概述
<div class="markdown-here-wrapper" data-md-url="https://i.cnblogs.com/EditPosts.aspx?postid=10312119">
<h1 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 24px; border-bottom: 2px solid #aaaaaa;">递归
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">一个函数在执行过程中一次或多次调用其本身便是递归,就像是俄罗斯套娃一样,一个娃娃里包含另一个娃娃。
:
<span class="hljs-keyword" style="color: #ebbbff;">if</span> low > high:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> <span class="hljs-keyword" style="color: #ebbbff;">False</span>
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
mid = (low + high) // <span class="hljs-number" style="color: #ffc58f;">2</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> target == data[mid]:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> <span class="hljs-keyword" style="color: #ebbbff;">True</span>
<span class="hljs-keyword" style="color: #ebbbff;">elif</span> target < data[mid]:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> binary_search(data,mid - <span class="hljs-number" style="color: #ffc58f;">1</span>)
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> binary_search(data,mid + <span class="hljs-number" style="color: #ffc58f;">1</span>,high)
<span class="hljs-keyword" style="color: #ebbbff;">if</span> low > high:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> <span class="hljs-keyword" style="color: #ebbbff;">False</span>
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
mid = (low + high) // <span class="hljs-number" style="color: #ffc58f;">2</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> target == data[mid]:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> <span class="hljs-keyword" style="color: #ebbbff;">True</span>
<span class="hljs-keyword" style="color: #ebbbff;">elif</span> target < data[mid]:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> binary_search(data,mid - <span class="hljs-number" style="color: #ffc58f;">1</span>)
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> binary_search(data,mid + <span class="hljs-number" style="color: #ffc58f;">1</span>,high)
<span class="hljs-keyword" style="color: #ebbbff;">if</span> low > high:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> <span class="hljs-keyword" style="color: #ebbbff;">False</span>
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
mid = (low + high) // <span class="hljs-number" style="color: #ffc58f;">2</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> target == data[mid]:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> <span class="hljs-keyword" style="color: #ebbbff;">True</span>
<span class="hljs-keyword" style="color: #ebbbff;">elif</span> target < data[mid]:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> binary_search(data,mid - <span class="hljs-number" style="color: #ffc58f;">1</span>)
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> binary_search(data,mid + <span class="hljs-number" style="color: #ffc58f;">1</span>,high)
:
一个序列的和,例如S[0:5],就像切片的范围一样
"""</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> start >= stop:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> <span class="hljs-number" style="color: #ffc58f;">0</span>
<span class="hljs-keyword" style="color: #ebbbff;">elif</span> start == stop - <span class="hljs-number" style="color: #ffc58f;">1</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> S[start]
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
mid = (start + stop) // <span class="hljs-number" style="color: #ffc58f;">2</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> binary_sum(S,mid) + binary_sum(S,mid,stop)
"""</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> start >= stop:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> <span class="hljs-number" style="color: #ffc58f;">0</span>
<span class="hljs-keyword" style="color: #ebbbff;">elif</span> start == stop - <span class="hljs-number" style="color: #ffc58f;">1</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> S[start]
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
mid = (start + stop) // <span class="hljs-number" style="color: #ffc58f;">2</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> binary_sum(S,mid) + binary_sum(S,mid,stop)
"""</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> start >= stop:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> <span class="hljs-number" style="color: #ffc58f;">0</span>
<span class="hljs-keyword" style="color: #ebbbff;">elif</span> start == stop - <span class="hljs-number" style="color: #ffc58f;">1</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> S[start]
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
mid = (start + stop) // <span class="hljs-number" style="color: #ffc58f;">2</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> binary_sum(S,mid) + binary_sum(S,mid,stop)
os
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def <span class="hljs-title" style="color: #7285b7;">disk_usage<span class="hljs-params" style="color: #ffc58f;">(path):
<span class="hljs-string" style="color: #d1f1a9;">"""
计算一个文件系统的磁盘使用情况,"""</span> total = <a href="https://www.jb51.cc/tag/ospath/" target="_blank" class="keywords">os.path</a>.getsize(path) <span class="hljs-keyword" style="color: #ebbbff;">if</span> <a href="https://www.jb51.cc/tag/ospath/" target="_blank" class="keywords">os.path</a>.isdir(path): <span class="hljs-keyword" style="color: #ebbbff;">for</span> filename <span class="hljs-keyword" style="color: #ebbbff;">in</span> os.listdir(path): childpath = <a href="https://www.jb51.cc/tag/ospath/" target="_blank" class="keywords">os.path</a>.join(path,filename) total += disk_usage(childpath) print(<span class="hljs-string" style="color: #d1f1a9;">'{0:<7}'</span>.format(total),path) <span class="hljs-keyword" style="color: #ebbbff;">return</span> total
"""</span>
total = <a href="https://www.jb51.cc/tag/ospath/" target="_blank" class="keywords">os.path</a>.getsize(path)
<span class="hljs-keyword" style="color: #ebbbff;">if</span> <a href="https://www.jb51.cc/tag/ospath/" target="_blank" class="keywords">os.path</a>.isdir(path):
<span class="hljs-keyword" style="color: #ebbbff;">for</span> filename <span class="hljs-keyword" style="color: #ebbbff;">in</span> os.listdir(path):
childpath = <a href="https://www.jb51.cc/tag/ospath/" target="_blank" class="keywords">os.path</a>.join(path,filename)
total += disk_usage(childpath)
print(<span class="hljs-string" style="color: #d1f1a9;">'{0:<7}'</span>.format(total),path)
<span class="hljs-keyword" style="color: #ebbbff;">return</span> total
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def <span class="hljs-title" style="color: #7285b7;">disk_usage<span class="hljs-params" style="color: #ffc58f;">(path):
<span class="hljs-string" style="color: #d1f1a9;">"""
计算一个文件系统的磁盘使用情况,
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def <span class="hljs-title" style="color: #7285b7;">disk_usage<span class="hljs-params" style="color: #ffc58f;">(path):
<span class="hljs-string" style="color: #d1f1a9;">"""
计算一个文件系统的磁盘使用情况,
"""</span>
total = <a href="https://www.jb51.cc/tag/ospath/" target="_blank" class="keywords">os.path</a>.getsize(path)
<span class="hljs-keyword" style="color: #ebbbff;">if</span> <a href="https://www.jb51.cc/tag/ospath/" target="_blank" class="keywords">os.path</a>.isdir(path):
<span class="hljs-keyword" style="color: #ebbbff;">for</span> filename <span class="hljs-keyword" style="color: #ebbbff;">in</span> os.listdir(path):
childpath = <a href="https://www.jb51.cc/tag/ospath/" target="_blank" class="keywords">os.path</a>.join(path,filename)
total += disk_usage(childpath)
print(<span class="hljs-string" style="color: #d1f1a9;">'{0:<7}'</span>.format(total),path)
<span class="hljs-keyword" style="color: #ebbbff;">return</span> total
:
斐波那契数列计算,返回的是一个元组
"""</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> n <= <span class="hljs-number" style="color: #ffc58f;">1</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> (n,<span class="hljs-number" style="color: #ffc58f;">0</span>)
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
(a,b) = fibonacci(n - <span class="hljs-number" style="color: #ffc58f;">1</span>)
<span class="hljs-keyword" style="color: #ebbbff;">return</span>(a + b,a)
"""</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> n <= <span class="hljs-number" style="color: #ffc58f;">1</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> (n,<span class="hljs-number" style="color: #ffc58f;">0</span>)
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
(a,b) = fibonacci(n - <span class="hljs-number" style="color: #ffc58f;">1</span>)
<span class="hljs-keyword" style="color: #ebbbff;">return</span>(a + b,a)
"""</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> n <= <span class="hljs-number" style="color: #ffc58f;">1</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> (n,<span class="hljs-number" style="color: #ffc58f;">0</span>)
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
(a,b) = fibonacci(n - <span class="hljs-number" style="color: #ffc58f;">1</span>)
<span class="hljs-keyword" style="color: #ebbbff;">return</span>(a + b,a)
:
print( + str(n) + 调用')
n +=
limitless(n)
limitless(<span class="hljs-number" style="color: #ffc58f;">1)
limitless(<span class="hljs-number" style="color: #ffc58f;">1)
limitless(<span class="hljs-number" style="color: #ffc58f;">1)
一个修改限制的方式
sys
:
print( + str(n) + 调用')
n +=
limitless(n)
print(sys.getrecursionlimit())<span class="hljs-comment" style="color: #7285b7;">#1000
sys.setrecursionlimit(<span class="hljs-number" style="color: #ffc58f;">2000)
limitless(<span class="hljs-number" style="color: #ffc58f;">1)
print(sys.getrecursionlimit())<span class="hljs-comment" style="color: #7285b7;">#1000
sys.setrecursionlimit(<span class="hljs-number" style="color: #ffc58f;">2000)
limitless(<span class="hljs-number" style="color: #ffc58f;">1)
print(sys.getrecursionlimit())<span class="hljs-comment" style="color: #7285b7;">#1000
sys.setrecursionlimit(<span class="hljs-number" style="color: #ffc58f;">2000)
limitless(<span class="hljs-number" style="color: #ffc58f;">1)
调用,但这个深度显然不是设置多少就是多少,毕竟还有计算机cpu与内存的限制,比如吧深度改为10000,那么运行后
查询-1073741571发现是递归栈溢出的问题。
函数调用中,会使用一个栈帧来保存当前调用的函数的信息,如输入参数、返回值空间、计算表达式时用到的临时存储空间、函数调用时保存的状态信息以及输出参数。因此在递归的调用中,这种未执行完的函数会一层一层的占用大量的栈帧。如果将递归的调用放到函数执行的最后一步,那么执行完这步,该次函数的栈帧就会释放,调用函数的新栈帧就会替换掉之前的栈帧,所以无论调用的深度有多少次,都只会占用一个栈帧,那也就不会发生栈溢出的问题。这就是尾递归。
调用的返回值必须立即返回。
一个阶乘递归函数举例
:
函数
"""</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> n == <span class="hljs-number" style="color: #ffc58f;">0</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> <span class="hljs-number" style="color: #ffc58f;">1</span>
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> n * factorial(n - <span class="hljs-number" style="color: #ffc58f;">1</span>)
"""</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> n == <span class="hljs-number" style="color: #ffc58f;">0</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> <span class="hljs-number" style="color: #ffc58f;">1</span>
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> n * factorial(n - <span class="hljs-number" style="color: #ffc58f;">1</span>)
"""</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> n == <span class="hljs-number" style="color: #ffc58f;">0</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> <span class="hljs-number" style="color: #ffc58f;">1</span>
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> n * factorial(n - <span class="hljs-number" style="color: #ffc58f;">1</span>)
:
"""</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> n < <span class="hljs-number" style="color: #ffc58f;">0</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> <span class="hljs-number" style="color: #ffc58f;">0</span>
<span class="hljs-keyword" style="color: #ebbbff;">elif</span> n == <span class="hljs-number" style="color: #ffc58f;">0</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> <span class="hljs-number" style="color: #ffc58f;">1</span>
<span class="hljs-keyword" style="color: #ebbbff;">elif</span> n == <span class="hljs-number" style="color: #ffc58f;">1</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> res
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
<span class="hljs-keyword" style="color: #ebbbff;">return</span> facttail(n - <span class="hljs-number" style="color: #ffc58f;">1</span>,n *res)
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">这个函数比之前那个还多了个res,第一种每次调用完要乘n,这里的res就起了相同的作用,由于尾递归每一层的栈帧要释放,所以通过res来作为相乘的过程。我个人认为尾递归的难度就在于参数的设计,因为它的前提条件就是调用后什么也不再执行了,所以要作为传递的东西就得提前通过参数设计传递,总之要想设计一个尾递归的算法还是需要好好思考一下的。
如果您也喜欢它,动动您的小指点个赞吧