{Algo}为什么我们难以理解递归

[pongba]

两个简单的认知学原因：

1. 我们的工作记忆只能存放7加减1个items。（这里）你不妨在大脑中模拟一下汉诺塔递归程序的运行过程，看看需要用多少记忆空间。（我敢保证三层递归就"溢出"了）
2. 语意相同的item被存放在同样的突触连接中。（关于大脑与记忆的书中常用这样的例子：你搬家之后，有了新号码。一开始你总是拨成老号码，记不住新号码。而一旦记住了新号码，老号码又难以记得了。——似乎是《找寻逝去的自我》，我记不清是哪本书了。）而一个递归函数中的各个局部变量语意都是相同的，所以会互相混淆——它们名字都是i，你叫我怎么区分噻？

其实最主要还是第一点。

如何理解递归？也很简单，像理解数学归纳法那样理解：第一步，先证明base case的正确性。第二步，假设第n层都是正确的，证明n+1层仍然保持了正确性的invariants（不变式）。

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[pongba]

2008/7/8 pongba <pon...@gmail.com>:

两个简单的认知学原因：

1. 我们的工作记忆只能存放7加减1个items。（这里）你不妨在大脑中模拟一下汉诺塔递归程序的运行过程，看看需要用多少记忆空间。（我敢保证三层递归就"溢出"了）

更正，是7加减2个items。ironically记错了..

[hayate]

我连2位数乘法的心算都困难，很沮丧地对同学说，我的栈好小啊。

2008/7/8 pongba <pon...@gmail.com>:

[ConcreteVitamin]

两位数的乘法自己想象一个竖式图出来会困难吗...

-------------About Me-------------
ConcreteVitamin: 一个热爱生活, 自由, 美剧, ACG, 算法, 数学, 摄影等等事物的废柴.
Blog - ConcreteVitamin 的小石屋:
http://blog.concretevitamin.com.cn

2008/7/8 hayate <haya...@gmail.com>:

[oslv lv]

感觉真的只能以数学归纳法来理解递归的正确性：确定最基本项的存在，然后证明第n项可以被第n-1项的存在而存在。可是要我设计和理解一个递归程序……

我当年是没弄懂数学归纳法的，但当见到了递归后，我觉得数学归纳法好简单哦…

 

[hayate]

不困难 但是我记不住啊

2008/7/8 ConcreteVitamin <concret...@gmail.com>:

[Lich_Ray]

On Tue, 8 Jul 2008 10:53:05 +0800
pongba <pon...@gmail.com> wrote:

> 两个简单的认知学原因：
>
> 1. 我们的工作记忆只能存放7加减1个items。（这里<http://en.wikipedia.org/wiki/The_Magical_Number_Seven%2C_Plus_or_Minus_Two>

> ）你不妨在大脑中模拟一下汉诺塔递归程序的运行过程，看看需要用多少记忆空间。（我敢保证三层递归就"溢出"了）
> 2.

> 语意相同的item被存放在同样的突触连接中。（关于大脑与记忆的书中常用这样的例子：你搬家之后，有了新号码。一开始你总是拨成老号码，记不住新号码。而一旦记住了新号码，老号码又难以记得了。----似乎是《找寻逝去的自我》，我记不清是哪本书了。）而一个递归函数中的各个局部变量语意都是相同的，所以会互相混淆----它们名字都是i，你叫我怎么区分噻？

>
> 其实最主要还是第一点。
>
> 如何理解递归？也很简单，像理解数学归纳法那样理解：第一步，先证明base
> case的正确性。第二步，假设第n层都是正确的，证明n+1层仍然保持了正确性的invariants（不变式）。
>
> --
> 刘未鹏(pongba)|C++的罗浮宫
> http://blog.csdn.net/pongba
> TopLanguage
> http://groups.google.com/group/pongba
>
> >

为什么我难以理解循环...

--
Ray Stinger, nickname Lich_Ray
God is in his heaven, all's right with the world.
-------------------------------------------------
let focus = 'computing' in where:
http://lichray.javaeye.com
let focus = 'computing' in here:
http://let-in.blogspot.com

[Henry Read]

不会吧，循环不是非常好理解吗？

2008/7/8 Lich_Ray <solo...@gmail.com>:

[谷祖超]

我记得很小的时候用QB编程，当时很难理解循环是干吗的，主要是不理解循环下标和每次循环体的任务。

在 08-7-8，Henry Read<henr...@gmail.com> 写道：

[殷远超]

相对来说，循环还是好理解的。我当时就想，早上起来上课，每节课我都记住它是第几节，记为n，当n==7时，就终止循环。至于课程[n],我从来不关心。
殷远超 http://www.yinux.com

2008/7/8 谷祖超 <gzc...@gmail.com>:

[ConcreteVitamin]

一开始学编程我对递归也比较郁闷.

后来发现, 递归过程的参数选择的好坏对理解这个递归程序是有很大帮助的.

-------------About Me-------------
ConcreteVitamin: 一个热爱生活, 自由, 美剧, ACG, 算法, 数学, 摄影等等事物的废柴.
Blog - ConcreteVitamin 的小石屋:
http://blog.concretevitamin.com.cn

2008/7/9 殷远超 <yinyu...@gmail.com>:

[ConcreteVitamin]

不好意思... 好像发了一个病句...

应该是: "递归过程的参数选择好了对理解这个递归程序是有很大帮助的"

-------------About Me-------------
ConcreteVitamin: 一个热爱生活, 自由, 美剧, ACG, 算法, 数学, 摄影等等事物的废柴.
Blog - ConcreteVitamin 的小石屋:
http://blog.concretevitamin.com.cn

2008/7/9 ConcreteVitamin <concret...@gmail.com>:

[ZelluX]

小时候刚学编程的时候习惯用循环，后来接触递归多了觉得递归更简单清晰

On Jul 8, 10:53 am, pongba <pon...@gmail.com> wrote:
> 两个简单的认知学原因：
>

> 1. 我们的工作记忆只能存放7加减1个items。（这里<http://en.wikipedia.org/wiki/The_Magical_Number_Seven%2C_Plus_or_Minu...>

> ）你不妨在大脑中模拟一下汉诺塔递归程序的运行过程，看看需要用多少记忆空间。（我敢保证三层递归就"溢出"了）
> 2.

> 语意相同的item被存放在同样的突触连接中。（关于大脑与记忆的书中常用这样的例子：你搬家之后，有了新号码。一开始你总是拨成老号码，记不住新号码。而一旦记住了新号码，老号码又难以记得了。----似乎是《找寻逝去的自我》，我记不清是哪本书了。）而一个递归函数中的各个局部变量语意都是相同的，所以会互相混淆----它们名字都是i，你叫我怎么区分噻？

[fxc...@gmail.com]

我也是，请问有多少人可以心算这个，直接算，不用改成加法。

On Jul 8, 10:38 pm, hayate <hayate...@gmail.com> wrote:
> 不困难 但是我记不住啊
>
> 2008/7/8 ConcreteVitamin <concretevita...@gmail.com>:

>
>
>
> > 两位数的乘法自己想象一个竖式图出来会困难吗...
>
> > -------------About Me-------------
> > ConcreteVitamin: 一个热爱生活, 自由, 美剧, ACG, 算法, 数学, 摄影等等事物的废柴.
> > Blog - ConcreteVitamin 的小石屋:
> >http://blog.concretevitamin.com.cn
>

> > 2008/7/8 hayate <hayate...@gmail.com>:

>
> > 我连2位数乘法的心算都困难，很沮丧地对同学说，我的栈好小啊。
>
> >> 2008/7/8 pongba <pon...@gmail.com>:
>
> >>> 2008/7/8 pongba <pon...@gmail.com>:
>
> >>>> 两个简单的认知学原因：
>

> >>>> 1. 我们的工作记忆只能存放7加减1个items。（这里<http://en.wikipedia.org/wiki/The_Magical_Number_Seven%2C_Plus_or_Minu...>

> >>>> ）你不妨在大脑中模拟一下汉诺塔递归程序的运行过程，看看需要用多少记忆空间。（我敢保证三层递归就"溢出"了）
>
> >>> 更正，是7加减2个items。ironically记错了..
>
> >>> --
> >>> 刘未鹏(pongba)|C++的罗浮宫
> >>>http://blog.csdn.net/pongba
> >>> TopLanguage

> >>>http://groups.google.com/group/pongba- Hide quoted text -
>
> - Show quoted text -

[windstorm]

两位数乘法，用原始的错位相加，是最笨的心算法。

无论是分解法，加整还是减整，练熟了都比笔算快

----------------------------------------------------------------------------------
Yours Sincerely
Kun

blog: www.forwind.cn

2008/7/9 fxc...@gmail.com <fxc...@gmail.com>:

[ConcreteVitamin]

不用改成加法什么意思?

就算是列竖式也要改成加法啊...

-------------About Me-------------
ConcreteVitamin: 一个热爱生活, 自由, 美剧, ACG, 算法, 数学, 摄影等等事物的废柴.
Blog - ConcreteVitamin 的小石屋:
http://blog.concretevitamin.com.cn

2008/7/9 fxc...@gmail.com <fxc...@gmail.com>:

[pongba]

2008/7/9 fxc...@gmail.com <fxc...@gmail.com>:

我也是，请问有多少人可以心算这个，直接算，不用改成加法。

有一个技巧：在脑海中想像一张白纸，想想自己拿着笔将结果写在纸上，就如同用纸笔计算一样。
原理是利用了视觉皮层的存储空间。
当然，还是比不上真正写在纸上的刺激强的，想像中的刺激总是打了个折扣，但总比没有好。

我有一次在书店里转悠，看到四本书，我想记下来回去再网上查，但手头没有纸笔，于是使用了一下古希腊人早就发明的空间记忆法：记住自己是站在书店的什么方位朝向哪边，看到那个书所在的什么地方的。简言之就是把周围环境线索连带着都记下来，结果回去一想，真是历历在目，到现在我都还能够记得起来，而且其它几本在他们旁边的书也大概都记得。
原理是利用海马的空间记忆的强大能力，提供大量的记忆提取线索。

还有比如气味记忆：如果学习某个东西的时候，环境中有一种比较奇特的味道。那么，当回忆的时候重放这种味道就会有助于回忆起当初记忆的东西。此外还有音乐：有一段时间我看古龙的小说的时候总是开着某段音乐，后来每当听到这段音乐，脑海中就泛起看古龙小说时的那种感觉。

[fxc...@gmail.com]

就是按照一般的竖式算法，不用其他技巧

On Jul 9, 12:49 pm, ConcreteVitamin <concretevita...@gmail.com> wrote:
> 不用改成加法什么意思?
>
> 就算是列也要改成加法啊...

> > > >>>http://groups.google.com/group/pongba-Hide quoted text -
>
> > > - Show quoted text -- Hide quoted text -

[fxc...@gmail.com]

好像就是对数字比敏感，记不住。。。

On Jul 9, 12:52 pm, pongba <pon...@gmail.com> wrote:
> 2008/7/9 fxc...@gmail.com <fxc...@gmail.com>:
>
> > 我也是，请问有多少人可以心算这个，直接算，不用改成加法。
>
> 有一个技巧：在脑海中想像一张白纸，想想自己拿着笔将结果写在纸上，就如同用纸笔计算一样。
> 原理是利用了视觉皮层的存储空间。
> 当然，还是比不上真正写在纸上的刺激强的，想像中的刺激总是打了个折扣，但总比没有好。
>

> 我有一次在书店里转悠，看到四本书，我想记下来回去再网上查，但手头没有纸笔，于是使用了一下古希腊人早就发明的空间记忆法：记住自己是站在书店的什么方位朝向-哪边，看到那个书所在的什么地方的。简言之就是把周围环境线索连带着都记下来，结果回去一想，真是历历在目，到现在我都还能够记得起来，而且其它几本在他们旁边-的书也大概都记得。
> 原理是利用海马的空间记忆的强大能力，提供大量的记忆提取线索。
>
> 还有比如气味记忆：如果学习某个东西的时候，环境中有一种比较奇特的味道。那么，当回忆的时候重放这种味道就会有助于回忆起当初记忆的东西。此外还有音乐：有一-段时间我看古龙的小说的时候总是开着某段音乐，后来每当听到这段音乐，脑海中就泛起看古龙小说时的那种感觉。

[Lich_Ray]

很多人都认为递归需要栈，所以难理解；其实在理解的过程中，递归是不需要栈的。真正需要理解时栈的是循环。从循环中你看不出任何逻辑，只能从注释中知道它想干什么。

[heroboy]

相比其它的parser方法，递归下降还是最容易理解的。

[donglongchao]

都怪我们的大脑不是堆栈型的啊。呵呵。

On 7月8日, 上午11时31分, hayate <hayate...@gmail.com> wrote:
> 我连2位数乘法的心算都困难，很沮丧地对同学说，我的栈好小啊。
>
> 2008/7/8 pongba <pon...@gmail.com>:
>
>
>
>
>
> > 2008/7/8 pongba <pon...@gmail.com>:
>
> >> 两个简单的认知学原因：
>

> >> 1. 我们的工作记忆只能存放7加减1个items。（这里<http://en.wikipedia.org/wiki/The_Magical_Number_Seven%2C_Plus_or_Minu...>

> >> ）你不妨在大脑中模拟一下汉诺塔递归程序的运行过程，看看需要用多少记忆空间。（我敢保证三层递归就"溢出"了）
>
> > 更正，是7加减2个items。ironically记错了..
>
> > --
> > 刘未鹏(pongba)|C++的罗浮宫
> >http://blog.csdn.net/pongba
> > TopLanguage

> >http://groups.google.com/group/pongba- 隐藏被引用文字 -
>
> - 显示引用的文字 -

[Henry Read]

还是人脑好。

2008/7/11 donglongchao <donglo...@163.com>:

[EC]

注：我没做过测试，也实不敢说精通递归。

我觉得递归，没有想象中的那么复杂，理解pongba说的汉诺塔（HNT）问题：
1、很显然，如果把HNT看成一组移动的物体，由于思维惯性（好像科学上称这些叫惰性思维），是较难把握，但如果你把这些移动想象成“轨迹”（这就有点
像一个游戏：开始的时候显示出目标，然后迅速的屏幕上左、右移动，最后让你找出target，这个游戏和HNT很相似，这样的话，大脑对处理的问题又降
低了一个级别）。

2、简单性递归（SR）：把逻辑部分和记忆部分进行分离，也就是说，SR中的逻辑部分，是一个周期规律，记忆部分是周期规律的结果。

3、复杂性递归（CR）：这里没有过多的逻辑（意义上的，如果真能找到逻辑，那么很可能是一台计算机）。暂时有一个不太成熟的办法，能提高效率，不过，
等我想得较明了了再说吧。

[silwile]

2008/7/9 pongba <pon...@gmail.com>:

2008/7/9 fxc...@gmail.com <fxc...@gmail.com>:

我也是，请问有多少人可以心算这个，直接算，不用改成加法。

有一个技巧：在脑海中想像一张白纸，想想自己拿着笔将结果写在纸上，就如同用纸笔计算一样。
原理是利用了视觉皮层的存储空间。
当然，还是比不上真正写在纸上的刺激强的，想像中的刺激总是打了个折扣，但总比没有好。

我有一次在书店里转悠，看到四本书，我想记下来回去再网上查，但手头没有纸笔，于是使用了一下古希腊人早就发明的空间记忆法：记住自己是站在书店的什么方位朝向哪边，看到那个书所在的什么地方的。简言之就是把周围环境线索连带着都记下来，结果回去一想，真是历历在目，到现在我都还能够记得起来，而且其它几本在他们旁边的书也大概都记得。
原理是利用海马的空间记忆的强大能力，提供大量的记忆提取线索。

 

还有比如气味记忆：如果学习某个东西的时候，环境中有一种比较奇特的味道。那么，当回忆的时候重放这种味道就会有助于回忆起当初记忆的东西。此外还有音乐：有一段时间我看古龙的小说的时候总是开着某段音乐，后来每当听到这段音乐，脑海中就泛起看古龙小说时的那种感觉。

 这一段，pongba，难道你也看过 追忆似水年华 :D