尾递归=递归+迭代?
2023-09-27 14:25:26 时间
0 引言
平时见惯了递归和迭代,递归直观,但太占内存和时间,迭代运算快,但是不如递归代码简洁明了。那么可不可以把这两种算法的优点糅合在一起?答案是肯定的,尾递归就提供了这样一种机制。
1 尾递归是什么
简单地说,尾递归就是披着“递归”的外衣,却拥有一颗“迭代”的心。外观上看起来像递归,但内部进行了迭代的运算。下面举例说明。
2 阶乘示例
2.1 先看阶乘的迭代算法:
2.2 再看阶乘的递归算法:
2.3 最后看阶乘的尾递归算法:
3 斐波那契数列示例
3.1 先看斐波那契数列的迭代算法:
3.2 再看斐波那契数列的递归算法:
3.3 最后看斐波那契数列的尾递归算法:
小结
通过示例可以看出,尾递归都是带着一个“迭代变量”不断向深处递归,相当于边递归,边计算,等递归完成时,结果也计算出来了。值得一提的是尾递归只是借了递归的外壳,本质还是在迭代,所以在效率上,应该是与迭代相仿的。
相关文章
- Python 迭代器,错误、异常处理
- 关于jQuery隐式迭代
- C#,二叉搜索树(Binary Search Tree)的迭代方法与源代码
- C++第10周项目2扩展之2参考——迭代求和
- 《剑指offer》之“翻转单链表”递归、迭代、双指针解题
- C++中防止STL中迭代器失效——map/set等关联容器——vector/list/deque等序列容器—如何防止迭代器失效—即erase()的使用
- 递归快还是循环(迭代)快?
- [js高手之路] es6系列教程 - 迭代器与生成器详解
- LeetCode之024两两交换链表中的节点(相关话题:链表递归迭代)
- NYOJ_94 cigarettes 递归VS迭代
- python第三十六课——1.可迭代对象