使用Python语言理解递归 -清零世界

概述

<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;">递归
一个函数在执行过程中一次或多次调用其本身便是递归，就像是俄罗斯套娃一样，一个娃娃里包含另一个娃娃。

 :
    
<span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> low > high:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> <span class="hljs-keyword" style="color: #ebbbff;"&gt;False</span>
<span class="hljs-keyword" style="color: #ebbbff;"&gt;else</span>:
    mid = (low + high) // <span class="hljs-number" style="color: #ffc58f;"&gt;2</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> target == data[mid]:
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> <span class="hljs-keyword" style="color: #ebbbff;"&gt;True</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;elif</span> target < data[mid]:
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> binary_search(data,mid - <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>)
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;else</span>:
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> binary_search(data,mid + <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>,high)

<span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> low > high:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> <span class="hljs-keyword" style="color: #ebbbff;"&gt;False</span>
<span class="hljs-keyword" style="color: #ebbbff;"&gt;else</span>:
    mid = (low + high) // <span class="hljs-number" style="color: #ffc58f;"&gt;2</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> target == data[mid]:
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> <span class="hljs-keyword" style="color: #ebbbff;"&gt;True</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;elif</span> target < data[mid]:
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> binary_search(data,mid - <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>)
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;else</span>:
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> binary_search(data,mid + <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>,high)

<span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> low > high:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> <span class="hljs-keyword" style="color: #ebbbff;"&gt;False</span>
<span class="hljs-keyword" style="color: #ebbbff;"&gt;else</span>:
    mid = (low + high) // <span class="hljs-number" style="color: #ffc58f;"&gt;2</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> target == data[mid]:
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> <span class="hljs-keyword" style="color: #ebbbff;"&gt;True</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;elif</span> target < data[mid]:
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> binary_search(data,mid - <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>)
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;else</span>:
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> binary_search(data,mid + <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>,high)

 :
    一个序列的和，例如S[0:5],就像切片的范围一样
"""</span>

<span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> start >= stop:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>
<span class="hljs-keyword" style="color: #ebbbff;"&gt;elif</span> start == stop - <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> S[start]
<span class="hljs-keyword" style="color: #ebbbff;"&gt;else</span>:
    mid = (start + stop) // <span class="hljs-number" style="color: #ffc58f;"&gt;2</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> binary_sum(S,mid) + binary_sum(S,mid,stop)

"""</span>

<span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> start >= stop:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>
<span class="hljs-keyword" style="color: #ebbbff;"&gt;elif</span> start == stop - <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> S[start]
<span class="hljs-keyword" style="color: #ebbbff;"&gt;else</span>:
    mid = (start + stop) // <span class="hljs-number" style="color: #ffc58f;"&gt;2</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> binary_sum(S,mid) + binary_sum(S,mid,stop)

"""</span>

<span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> start >= stop:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>
<span class="hljs-keyword" style="color: #ebbbff;"&gt;elif</span> start == stop - <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> S[start]
<span class="hljs-keyword" style="color: #ebbbff;"&gt;else</span>:
    mid = (start + stop) // <span class="hljs-number" style="color: #ffc58f;"&gt;2</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;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;"&gt;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;"&gt;for</span> filename <span class="hljs-keyword" style="color: #ebbbff;"&gt;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;"&gt;'{0:<7}'</span>.format(total),path)
<span class="hljs-keyword" style="color: #ebbbff;"&gt;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;"&gt;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;"&gt;for</span> filename <span class="hljs-keyword" style="color: #ebbbff;"&gt;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;"&gt;'{0:<7}'</span>.format(total),path)
<span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> total

def disk_usage(path):
"""
计算一个文件系统的磁盘使用情况，

"""</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;"&gt;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;"&gt;for</span> filename <span class="hljs-keyword" style="color: #ebbbff;"&gt;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;"&gt;'{0:<7}'</span>.format(total),path)
<span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> total

 :
    斐波那契数列计算，返回的是一个元组
"""</span>

<span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> n <= <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> (n,<span class="hljs-number" style="color: #ffc58f;"&gt;0</span>)
<span class="hljs-keyword" style="color: #ebbbff;"&gt;else</span>:
    (a,b) = fibonacci(n - <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>)
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span>(a + b,a)

"""</span>

<span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> n <= <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> (n,<span class="hljs-number" style="color: #ffc58f;"&gt;0</span>)
<span class="hljs-keyword" style="color: #ebbbff;"&gt;else</span>:
    (a,b) = fibonacci(n - <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>)
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span>(a + b,a)

"""</span>

<span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> n <= <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> (n,<span class="hljs-number" style="color: #ffc58f;"&gt;0</span>)
<span class="hljs-keyword" style="color: #ebbbff;"&gt;else</span>:
    (a,b) = fibonacci(n - <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>)
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span>(a + b,a)

 :
    print( + str(n) + 调用')
    n += 
     limitless(n)
limitless(<span class="hljs-number" style="color: #ffc58f;">1)

limitless(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())#1000 sys.setrecursionlimit(2000) limitless(1)

调用，但这个深度显然不是设置多少就是多少，毕竟还有计算机cpu与内存的限制，比如吧深度改为10000，那么运行后

查询-1073741571发现是递归栈溢出的问题。

函数调用中，会使用一个栈帧来保存当前调用的函数的信息，如输入参数、返回值空间、计算表达式时用到的临时存储空间、函数调用时保存的状态信息以及输出参数。因此在递归的调用中，这种未执行完的函数会一层一层的占用大量的栈帧。如果将递归的调用放到函数执行的最后一步，那么执行完这步，该次函数的栈帧就会释放，调用函数的新栈帧就会替换掉之前的栈帧，所以无论调用的深度有多少次，都只会占用一个栈帧，那也就不会发生栈溢出的问题。这就是尾递归。

调用的返回值必须立即返回。

一个阶乘递归函数举例

 :
    函数
"""</span>
<span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> n == <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>
<span class="hljs-keyword" style="color: #ebbbff;"&gt;else</span>:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> n * factorial(n - <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>)

"""</span>
<span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> n == <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>
<span class="hljs-keyword" style="color: #ebbbff;"&gt;else</span>:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> n * factorial(n - <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>)

"""</span>
<span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> n == <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>
<span class="hljs-keyword" style="color: #ebbbff;"&gt;else</span>:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> n * factorial(n - <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>)

 :
    """</span>

<span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> n < <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>
<span class="hljs-keyword" style="color: #ebbbff;"&gt;elif</span> n == <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>
<span class="hljs-keyword" style="color: #ebbbff;"&gt;elif</span> n == <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> res
<span class="hljs-keyword" style="color: #ebbbff;"&gt;else</span>:
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> facttail(n - <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>,n *res)

这个函数比之前那个还多了个res，第一种每次调用完要乘n，这里的res就起了相同的作用，由于尾递归每一层的栈帧要释放，所以通过res来作为相乘的过程。我个人认为尾递归的难度就在于参数的设计，因为它的前提条件就是调用后什么也不再执行了，所以要作为传递的东西就得提前通过参数设计传递，总之要想设计一个尾递归的算法还是需要好好思考一下的。

如果您也喜欢它,动动您的小指点个赞吧

使用Python语言理解递归

概述

分类汇总

您的鼓励是对我最大的支持