|
<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;">一个函数在执行过程中一次或多次调用其本身便是递归，就像是俄罗斯套娃一样，一个娃娃里包含另一个娃娃。
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">递归其实是程序设计语言学习过程中很快就会接触到的东西，但有关递归的理解可能还会有一些遗漏，下面对此方面进行更加深入的理解
<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;">这里根据递归调用的数量分为线性递归、二路递归与多重递归
<h3 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 20px; border-bottom: 1px 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;">如果一个递归调用最多开始一个其他递归调用，我们称之为线性递归。
<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)
<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，但他们是不同条件执行的，每次只能执行一次，所以是线性递归。
<h3 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 20px; border-bottom: 1px 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;">如果一个递归调用可以开始两个其他递归调用，我们称之为二路递归
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">例如：
:
"""</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)
<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
<h3 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 20px; border-bottom: 1px 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;">如果一个递归调用可以开始三个或者更多其他递归调用，我们称之为多重递归
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">例如：
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 = os.path.getsize(path)
<span class="hljs-keyword" style="color: #ebbbff;">if</span> os.path.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 = os.path.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
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">os.path.getsize为获得标识的文件或者目录使用的即时磁盘空间大小。我理解的是如果该标识的是一个文件，那么就是获得该文件的大小，如果是一个文件夹的话，那就是获得该文件夹的大小，但不包括文件夹里边的内容，就像是一个盒子中放了很多物品，但这里只计算了盒子的重量，但没有计算物品的重量，也就是计算了一个空盒子。所以这个递归函数中的递归调用次数取决于这一层文件或文件夹的数量，所以是多重递归。
<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;">递归的不足显然就是时间与空间的消耗，具体可以参考<a href="https://www.cnblogs.com/sfencs-hcy/p/10171457.html">https://www.cnblogs.com/sfencs-hcy/p/10171457.html ，这篇文章中使用了缓存的方法减少了斐波那契数列的计算消耗，在这里我们使用另一种方式来改善那种坏的递归：
:
"""</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)
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">将原来的二路递归改为了线性递归，减少了重复的计算。
<h1 id="python-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 24px; border-bottom: 2px solid #aaaaaa;">python的最大递归深度
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">每一次递归都会有资源的消耗，每一次连续的调用都会需要额外的内存，当产生无限递归时，那就意味着资源的迅速耗尽，这明显是不合理的。python为了避免这种现象，在设计时有意的限制了递归的深度，我们可以测试一下
:
print( + str(n) + )
n +=
limitless(n)
limitless(<span class="hljs-number" style="color: #ffc58f;">1 )
<blockquote style="margin: 1.2em 0px; border-left: 4px solid #dddddd; padding: 0px 1em; color: #777777; quotes: none;">
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">第988次调用第989次调用第990次调用第991次调用第992次调用第993次调用第994次调用第995次调用第996次调用Traceback (most recent call last): File “D:/github/Data-Structure/code/递归.py”,line 73,in limitless(1) File “D:/github/Data-Structure/code/递归.py”,line 70,in limitless return limitless(n) File “D:/github/Data-Structure/code/递归.py”,in limitless return limitless(n) [Previous line repeated 992 more times] File “D:/github/Data-Structure/code/递归.py”,line 68,in limitless print(‘第’ + str(n) + ‘次调用’)RecursionError: maximum recursion depth exceeded while calling a Python object
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)
<blockquote style="margin: 1.2em 0px; border-left: 4px solid #dddddd; padding: 0px 1em; color: #777777; quotes: none;">
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">第1994次调用第1995次调用第1996次调用Traceback (most recent call last): File “D:/github/Data-Structure/code/递归.py”,in limitless return limitless(n) [Previous line repeated 995 more times] File “D:/github/Data-Structure/code/递归.py”,in limitless print(‘第’ + str(n) + ‘次调用’)RecursionError: maximum recursion depth exceeded while calling a Python object
:
"""</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>)
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">上边这个是一个普通的递归，下面把他改成尾递归的形式
:
"""</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来作为相乘的过程。我个人认为尾递归的难度就在于参数的设计，因为它的前提条件就是调用后什么也不再执行了，所以要作为传递的东西就得提前通过参数设计传递，总之要想设计一个尾递归的算法还是需要好好思考一下的。
（编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
