- 论坛徽章:
- 0
|
本帖最后由 madaossan 于 2012-10-29 18:30 编辑
"人理解迭代,神理解递归".
To iterate is human, to recurse divine. ——L. Peter Deutsch
两个来自SICP的尾递归示例, 都是求n!的 :
这个是递归(a recursive procedure. it's "really" recursive):- (define (factorial n)
- (if (= n 1)
- 1
- (* n (factorial (- n 1)))))
复制代码 这个是"迭代的递归(fact-iter -- a recursive procedure, but an iterative process, say, linearly recursive)":- (define (factorial n)
- (fact-iter 1 1 n))
- (define (fact-iter product counter max-count)
- (if (> counter max-count)
- product
- (fact-iter (* counter product)
- (+ counter 1)
- max-count)))
复制代码 "迭代的递归"使得scheme没有for, while, do while.(试试用C写一个"迭代的递归").
此外, 比如求一个算术表达式的值, 这个算术表达式需要支持 + * ().- I -> num(num is a named regular expression, or a Language on a regular exp, represent a number)
- F -> I | (E)
- T -> F | T * F
- E -> T | E + T
复制代码 some a bit like recursive descent.
实际上我现在也不太会用递归, 它常让我混乱和痛苦无比. hanoi塔现在都还时常让我陷入混乱.
关于递归, 我以前干过的事情就是一步一步把递归过程画出来, C局部变量的状态被我用方框方框画了很多框, 直到整张A4纸画不下了, 然后对自己说瞧就是这样, 然后我觉得差不多啦, 然后等待下一次半天不知道怎么敲代码的时候到来.
update: 求算术表达式的那个, 原来的文法错了... 木有人发现么... |
|