有多少科班毕业的时候还不会递归？

madaossan

"人理解迭代,神理解递归".
To iterate is human, to recurse divine.          ——L. Peter Deutsch

两个来自SICP的尾递归示例, 都是求n!的 :

这个是递归(a recursive procedure. it's "really" recursive):

1. (define (factorial n)
   
2.   (if (= n 1)
   
3.       1
   
4.       (* n (factorial (- n 1)))))

复制代码

这个是"迭代的递归(fact-iter -- a recursive procedure, but an iterative process, say, linearly recursive)":

1. (define (factorial n)
   
2.   (fact-iter 1 1 n))
   
3. 
   
4. (define (fact-iter product counter max-count)
   
5.   (if (> counter max-count)
   
6.       product
   
7.       (fact-iter (* counter product)
   
8.                  (+ counter 1)
   
9.                  max-count)))

复制代码

"迭代的递归"使得scheme没有for, while, do while.(试试用C写一个"迭代的递归").

此外, 比如求一个算术表达式的值, 这个算术表达式需要支持 + * ().

1. I -> num(num is a named regular expression, or a Language on a regular exp, represent a number)
   
2. F -> I | (E)
   
3. T -> F | T * F
   
4. E -> T | E + T

复制代码

some a bit like recursive descent.

实际上我现在也不太会用递归, 它常让我混乱和痛苦无比. hanoi塔现在都还时常让我陷入混乱.

关于递归, 我以前干过的事情就是一步一步把递归过程画出来, C局部变量的状态被我用方框方框画了很多框, 直到整张A4纸画不下了, 然后对自己说瞧就是这样, 然后我觉得差不多啦, 然后等待下一次半天不知道怎么敲代码的时候到来.


update: 求算术表达式的那个, 原来的文法错了... 木有人发现么...

pandaiam

啥是科班啊..

我承认我刚毕业的时候不会递归..

file3

递归记住两点：
1.递归条件
2.递归推出条件

starwing83

楼上，有些递归，是不需要递归停止条件的。比如，很多语言可以通过递归，定义自然数的概念，然后就可以直接在这个基础上定义一个斐波拉契数的概念。然后如果我要取第10个斐波拉契数：

(prn (take 10 (fib)))

这就是函数式语言的递归。递归并不一定需要结束条件的。

captivated

回复 15# starwing83


    这应该就是我说的那个"迭代的递归"?

    不过fibonacci不是尾递归.

starwing83

回复 16# captivated


    额……我说的是SICP里面的介绍……

就是说，执行是延迟的，所以递归无所谓有没有结束，而是由外界决定结束条件，比如一个递归：

(defn natural-num [n] (lazy-seq (cons n (natural-num (+ n 1)))))

很好理解：什么是自然数列：即后面一个比前面一个大一的数列。注意是没有结束条件的。

那么，如果我要取前十个自然数呢？

(prn (take 10 (natural-num 1))
--> (1 2 3 4 5 6 7 8 9 10)

看到了么？因为我只取十个，所以只递归十次，如果我取无数个，就是无穷递归。当然我也不可能取无穷个了。这样的递归方式（惰性流），就是我说的不需要结束条件的递归。

OwnWaterloo

回复 16# captivated

不一样，一个说的是shape，一个说的是求值方式。fib也可以改成linear的shape。

至于求值方式。。。  自己写一个产生fib序列的定义。。。 然后化简(reduce)吧。。。
记得wikipedia里有提到多种化简策略么？


还是来点例子。。。

1. 
   
2. (define (double x) (+ x x))
   
3. (define (square x) (* x x))
   

复制代码

(square (double 3)) ; 可以优先化简inner (square (+ 3 3)) ; (square 6) ; (* 6 6) ; 36
; 也可以优先化简 outer (* (double 3) (double 3)) ; (* (+ 3 3) (+ 3 3)) ; (* 6 6) ; 36

前者就是strict的，没有终止条件的递归一旦开始化简是死循环。
后者就是non-strict的。 square函数被调用时， 它的参数并没有被化简(求值)， 而是当square定义里的*需要参数的值时， (double 3) 才被求值。


你再看看这个：

1. 
   
2. (define (f x a b) (if (= 0 x) (double a) (square b)))
   
3. (define (g x) (g (+ 1 x))
   
4. (f (* 2 6) (g 0) (+ 1 2))
   

复制代码

如果先outer， (f (* 2 6) (g 0) (+ 1 2)) 这个调用首先化简定义
(if (= 0 (* 2 6)) (double (g 0)) (square (+ 1 2)))
; 其实bool逻辑if, =,算术运算都可以用lambda演算表示， 那样可以看得更清楚。。。
; 这里就假设是strict语言里的if结构吧。。。 3个表达式， 第1个先被求值， 然后根据它的值，选择求值剩下两个中的一个。
首先会求值 (= 0 (* 2 6)) ; (= 0 12) ; #f
然后因为是#f， 所以就不需要 (g 0)，跳过， 只对(square (+ 1 2)) 求值。 (* (+ 1 2) (+ 1 2)) ; (* 3 3) ; 9
于是就没有死循环。


如果先inner， (f (* 2 6) (g 0) (+ 1 2)) 这个调用首先会化简它的参数，假设是由左到右吧。
(* 2 6) 得到 12， 然后是(g 0)， 然后就出不去了。。。
(g 0) -> (g (+ 1 0)) -> (g 1) -> (g (+ 1 1)) -> ...
其实顺序都无所谓，由右到左也行， 甚至乱序、并行都可以。
但只要在函数定义前先化简参数， (g 0)始终出不去， 就看不到f的定义。。。 看不到(g 0)其实是不被需要的。

captivated

回复 17# starwing83


    哦. 我还没看到那里. 你写的 defn, lazy-seq我都还不认识. 你写的natural-num我还是理解不能. 是后面的内容还是(scheme的)不同的解释器实现?

    第一章里面有讲Applicative order versus normal order, 就是说应用序是一般的顺序(先求值再替换), normal order就是先替换, 最后归约, 所以一般所说的惰性求值是不是就是normal order?

    不过书上似乎也说解释器使用何种求值顺序是没关系的, 只要能得到正确结果 -- 所以有个问题, 确实保证不管如何定义函数, 这两种求值序都能得到相同的结果? 求解释... 同时书上也提到

1. (define (p) (p))
   
2. 
   
3. (define (test x y)
   
4.   (if (= x 0)
   
5.       0
   
6.       y))
   
7. 
   
8. ;; 用来测试是applicative-order还是normal-order
   
9. (test 0 (p))
   

复制代码

这段代码可以决定解释是applicative-order还是normal-order. 帮忙解释下这个, 我感觉我死循环了...

    我用来练习的解释器是MIT/GNU Scheme, 就是书上推荐的.

captivated

回复 18# OwnWaterloo

    嗯, 所以是说的我LS说的那个么?

Exercise 1.5. Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with is using applicative-order evaluation or normal-order evaluation. He defines the following two procedures:

(define (p) (p))

(define (test x y)
  (if (= x 0)
      0
      y))

Then he evaluates the expression

(test 0 (p))

What behavior will Ben observe with an interpreter that uses applicative-order evaluation? What behavior will he observe with an interpreter that uses normal-order evaluation? Explain your answer. (Assume that the evaluation rule for the special form if is the same whether the interpreter is using normal or applicative order: The predicate expression is evaluated first, and the result determines whether to evaluate the consequent or the alternative expression.)

也就是说,
如果是applicative-order,
那么也就是 (test 0 (p)), 这里(p)是一个函数要先求值. 问题是这个函数的求值结果还是一个函数, 也就是还是(p). 那这样是死循环了.

如果是normal-order,
那么
test(0, (p)) --> (if (= 0 0) 0 (p)) --> reduce --> 0

======================

是这样的么?