《Hello算法》开卷有益——迭代和递归算法
<div class='showpostmsg'><p> <br />计算机中算法是个奇怪的东西。首先是极其重要，生活中各种问题的解决都需要使用到算法，计算机软件就是一个由算法构成的庞大工程，但另一方面，它又暗暗隐藏，平时能看见的各种软件都已经将算法隐藏在其中了，可以无需了解算法的实现，而且使用各种软件。不了解算法也可以编程，但是想编写出优秀的程序，必须了解算法。</p>
<p>关于迭代和递归，书中给了个例子：给定一个斐波那契数列 0,1,1,2,3,5,8,13,… ，求该数列的第N个数字。</p>
<p>使用递归的例子：对于递归来说，终止条件至关重要，如果没有终止条件，则会陷入“鸡生蛋，蛋生鸡”的无限循环之中……</p>
<pre>
<code class="language-python">def fib(n: int) -> int:
"""斐波那契数列：递归"""
# 终止条件 f(1) = 0, f(2) = 1
if n == 1 or n == 2:
return n - 1
# 递归调用 f(n) = f(n-1) + f(n-2)
res = fib(n - 1) + fib(n - 2)
# 返回结果 f(n)
return res</code></pre>
<p>使用迭代则比较好理解，从初始条件出发，一直计算到满足终止条件即可。日常中解决问题的思路以迭代居多。</p>
<hr />
<p>书中给出了迭代和递归的比较图。</p>
<p align="center">迭代与递归特点对比</p>
<table>
<thead>
<tr>
<th> </th>
<th>迭代</th>
<th>递归</th>
</tr>
</thead>
<tbody>
<tr>
<td>实现方式</td>
<td>循环结构</td>
<td>函数调用自身</td>
</tr>
<tr>
<td>时间效率</td>
<td>效率通常较高，无函数调用开销</td>
<td>每次函数调用都会产生开销</td>
</tr>
<tr>
<td>内存使用</td>
<td>通常使用固定大小的内存空间</td>
<td>累积函数调用可能使用大量的栈帧空间</td>
</tr>
<tr>
<td>适用问题</td>
<td>适用于简单循环任务，代码直观、可读性好</td>
<td>适用于子问题分解，如树、图、分治、回溯等，代码结构简洁、清晰</td>
</tr>
</tbody>
</table>
<p>通过对比可以看出，递归在时间效率和内存使用是都劣于迭代，但是迭代处理的问题，通常会在处理前对问题有清晰的路径和方法，算法中使用循环去解决问题。而递归则通常对问题只有收敛的条件，具体解决过程负责或冗长，使用递归不停地对函数自身进行调用，直至解决完问题，对于复杂问题有着优势。</p>
<p> </p>
</div><script> var loginstr = '<div class="locked">查看本帖全部内容，请<a href="javascript:;" style="color:#e60000" class="loginf">登录</a>或者<a href="https://bbs.eeworld.com.cn/member.php?mod=register_eeworld.php&action=wechat" style="color:#e60000" target="_blank">注册</a></div>';
if(parseInt(discuz_uid)==0){
(function($){
var postHeight = getTextHeight(400);
$(".showpostmsg").html($(".showpostmsg").html());
$(".showpostmsg").after(loginstr);
$(".showpostmsg").css({height:postHeight,overflow:"hidden"});
})(jQuery);
} </script><script type="text/javascript">(function(d,c){var a=d.createElement("script"),m=d.getElementsByTagName("script"),eewurl="//counter.eeworld.com.cn/pv/count/";a.src=eewurl+c;m.parentNode.insertBefore(a,m)})(document,523)</script> <p>表达是挺简便的，但是计算的时候是不是会反复调用函数，是不是调用的数据越大，迭代的次数越大，消耗的时间就越久？</p>
页:
[1]