递归思想为什么是编程的基本思想,它效率很高吗?


Author: Kimmy

递归思想为什么是编程的基本思想,它效率很高吗?

知乎链接


递归是基本思想,是因为他能够直白的表示出来运算过程,题主给出来的斐波那契函数,在没有通项公式的情况下,用递推公式简单直观,一目了然地描述了问题,同时,因为这种递推关系,程序会自动帮你去做计算。


但是递归的效率通常是不高的。一方面,频繁的函数调用导致重复压栈出栈,有很多额外开销(当然,尾调用优化可以解决一部分这种问题),另外,像fib这种函数,在同一个函数调用中有多个递归点,展开之后会是一个复杂的树状递归调用图,在没有做记忆处理的情况下,其中的重复运算带来的时间和空间开销都非常的大。所以,这样一个看似简单的函数,耗时久再正常不过了。

当然有一些技巧可以手动对其做一些优化,比如,把树状递归改写成线性递归调用的尾递归(符合尾调用形式的递归),再进一步就可以利用编译器,或者是手动进行尾调用优化。这些基本的技巧其实对你理解编程和计算都有很大的帮助,建议可以多练习一下。


另外推荐两本书,其中涉及了相关的内容。一本是大名鼎鼎的SICP,另外一本是 Element of Programming(中译本叫《编程原本》),可以拿来做参考。


以上。

创建时间:2018-05-03 最近更新时间:2024-07-26