使用Python语言理解递归

<div class="markdown-here-wrapper" data-md-url="https://i.cnblogs.com/EditPosts.aspx?postid=10312119"&gt;
<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;"&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)

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">虽然在代码中有两个binary_search，但他们是不同条件执行的，每次只能执行一次，所以是线性递归。

"""</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)

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">这个递归每次执行都会调用两次该函数，所以说是二路递归，每次递归后，范围缩小一半，所以该递归的深度是1+logn

<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 = os.path.getsize(path)
<span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> os.path.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 = os.path.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)

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!