本期介绍🍖
主要介绍：什么是斐波那契数列，递归实现求斐波那契数列第n项值，递归法为什么不适合求斐波那契数，用迭代法实现求斐波那契数列的值👀。
目录🍖
前言🍖
斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21，34，55，89…这个数列从第3项开始，每一项都等于前两项之和。
递归法实现🍖
递归法思路：从斐波那契数列的第n项开始（除第1项和第2项），然后通过每一项都等于前两项之和，疯狂递归直至递归到第1项或第2项才停止。
|
1 |
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string"><stdio.h></span></span> <span class="token keyword">int</span> <span class="token function">Fib</span><span class="token punctuation">(</span><span class="token keyword">int</span> num<span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">if</span> <span class="token punctuation">(</span>num <span class="token operator"><=</span> <span class="token number">2</span><span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> <span class="token function">Fib</span><span class="token punctuation">(</span>num <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">Fib</span><span class="token punctuation">(</span>num <span class="token operator">-</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">int</span> n <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"请输入要打印第几项斐波那契数："</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span> <span class="token operator">&</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">int</span> ret <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> ret <span class="token operator">=</span> <span class="token function">Fib</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d\n"</span><span class="token punctuation">,</span> ret<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> |
为什么递归法不适合求斐波那契数列🍖
因为该方法的效率实在是太低了，不信你就试试求斐波那契数列的第40项，当你去执行的时候你就会发现，计算机会等待一段时间才会给你答案。这段时间计算机可没在偷懒，它在死命的计算呢，那为什么计算机会要计算那么久呢？
因为在递归求斐波那契数值的过程中会重复的去计算某一项值很多次，且项数越小被重复计算的次数越多。就如上图所示，第36项的值就被重复计算4次，而第3项达到了惊人的39088169次重复计算！！！可见用递归法来求斐波那契数列值是多么的低效。
迭代法实现🍖
除了递归法还可以通过迭代法来求第n项的斐波那契数列，因为不管是递归还是迭代其本质都是循环，无非就是正向思维和反向思维之区别。迭代法思路：从项斐波那契数的第1项开始，然后通过每一项都等于前两项之和，不断的迭代就可以递推出第n项斐波那契数的值了。
|
1 |
<span class="token keyword">int</span> <span class="token function">fib</span><span class="token punctuation">(</span><span class="token keyword">int</span> num<span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">int</span> sum <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">int</span> n1 <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">int</span> n2 <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">while</span> <span class="token punctuation">(</span>num <span class="token operator">>=</span> <span class="token number">3</span><span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> sum <span class="token operator">=</span> n1 <span class="token operator">+</span> n2<span class="token punctuation">;</span> n1 <span class="token operator">=</span> n2<span class="token punctuation">;</span> n2 <span class="token operator">=</span> sum<span class="token punctuation">;</span> num<span class="token operator">--</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> sum<span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span> <span class="token keyword">int</span> n <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"请输入要打印第几个斐波那契数："</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span> <span class="token operator">&</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">int</span> ret <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> ret <span class="token operator">=</span> <span class="token function">fib</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d\n"</span><span class="token punctuation">,</span> ret<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> |
总结🍖
在很多实际问题中，我们可以用递归来解决也可以用非递归来是解决，而有时用递归去解决问题的时候会存在一些问题，就譬如刚刚求斐波那契数列的问题的效率低下。所以碰到这类问题时我们就不能再使用递归的方法了，我们需要另辟蹊径从另一个角度来思考对策，就譬如迭代的方法。
这份博客👍如果对你有帮助，给博主一个免费的点赞以示鼓励欢迎各位🔎点赞👍评论收藏⭐️，谢谢！！！
如果有什么疑问或不同的见解，欢迎评论区留言欧👀。
微信扫一扫打赏
支付宝扫一扫打赏
