欢迎到来。若想注册,请私信知乎 王霄池。
多知乎(取自 孰为汝多知乎),一个意见强烈,观点极端的问答社区。解放知识,让人们认识世界、改造世界。

分类

最新提问 分类:自然科学 | 用户: (510 分)
重新分类 用户:

1个回答

0 投票
递归思想为什么是编程的基本思想?

因为否则我们就编不出来了。

它效率很高吗?

总体来说效率较低,天真的实现效率就更低了。


递归思想为什么是编程的基本思想?

假设需要你求斐波那契数列,而且这个数很大,那么你可能需要求助于计算机,编个程序来计算。

我们看看数列的定义

\begin{eqnarray} f_n= \begin{cases} 1, &n=1 \ \text{or} \ n=2 \cr f_{n-1}+f_{n-2}, & \text{otherwise} \end{cases} \end{eqnarray}

这个定义很简单。我们可以写出对应的JS代码

f = (n) => n == 1 || n == 2 ? 1 : f(n-1)+f(n-2)

很简洁。

效率却很低。f(42)就已经需要几秒钟了。

但在这里,效率是小问题。我们稍微修改一下代码:

f = (n) => f[n] ? f[n] : ( n == 1 || n == 2 ? (f[n]=1) : (f[n]=f(n-1)+f(n-2)) )

这里相当于加了个缓存。算过的,我们就不会再计算了。用空间换时间。

f(99)现在也是小意思了。

到现在为止我们只说了一个观点:递归函数用代码表示非常简洁。

在历史上,D神第一次提出了递归函数的实现方式。从此之后,很多用以往眼光看很复杂的编程问题立刻变得简单了(比如汉诺塔)。

但我以上花费那么多篇幅讲的观点,都只是小事。真正的大事是:一般认为,递归函数和可计算函数是重合的。

什么意思呢,意思就是:人类能计算的函数,只有递归函数这一种。如果一个函数不是递归函数,那么,它将是不可计算的!

举个很著名的例子:忙海狸问题。

设有一图灵机,初始纸带上全是0,字符集只有0和1,这个图灵机有n个状态(不算停机状态)。
已知这个图灵机一定会停机。
问这个图灵机最多能打印多少个1?

这个函数 \Sigma(n) 被称为忙海狸函数。这个函数就是不可计算的。

你可以自己算一下,显然 \Sigma(1)=1 ,然后,然后你就发现这个问题没那么简单。

递归效率很高吗?

那得看和谁相比。一般来说,比不过对应的循环。因为c语言的设计,在call函数的时候得pusha(保存寄存器)。所以调用函数的开销很大。

不过,在有尾递归优化的语言中,尾递归可以做到和循环的效率一样。

那么循环的效率最高喽?

也得看和谁比,一般来说,它比不上数学公式呀!

比如上面的斐波那契数列,你费尽心力改成了循环。那又如何?

你要是知道:

Fib(n)是与 \frac{\phi^{n}}{\sqrt{5}} 最接近的整数,其中 \phi = \frac{1+\sqrt{5}}{2}

这么一说,循环地位尴尬,比表现力比不过递归,比效率比不过公式。


当然了,青少年才吹牛逼,成年人都知道,每种方法都有其适用范围

你要是研究可计算性这种定性的问题,肯定是用递归(你不关心效率);你要是写C语言,那多用用循环(顺便贬低一下递归);你要是智商高,那么你就有资格推推公式,读读paper喽。

最新回答 用户: (510 分)
...