尾递归和续延

101 views
Skip to first unread message

Liutos

unread,
May 21, 2012, 10:54:15 AM5/21/12
to lis...@googlegroups.com
把普通的递归转换成尾递归有没有通用可复制的方法呢?

例如定义了一个计算列表长度的函数 (defun my-length (list) (if (null list) 0 (+ (my-length (cdr list)) 1)))。很明显,这是普通的递归函数定义,转换成尾递归也很简单,如下

(defun my-length (list)
  (labels ((rec (acc list)
         (if (null list)
         acc
         (rec (+ acc 1)
              (cdr list)))))
    (rec 0 list)))

本来加一的操作,也即(+ acc 1)这里的对acc的处理,应该是在原来的递归函数中的``上一层''调用中出现的,现在被放到了acc的计算中。加一的操作可以视为原来的递归函数中的再一次调用时的续延,可以看做一个匿名函数 (lambda (v) (+ v 1))。这样的话,就可以理解为,尾递归实际上就是将续延以某种方式保存在了再一次的递归函数调用中。在老赵的博客那里看到的更明显地使用续延的方式来计算斐波纳契数列的第n项的值的定义,原文为http://blog.zhaojie.me/2009/03/tail-recursion-and-continuation.html,我改为Lisp代码后是这样的

(defun factorial-continuation (n cont)
  (if (= 0 n)
      (funcall cont 1)
      (factorial-continuation (- n 1)
                  (lambda (r)
                (funcall cont (* n r))))))

(defun factorial-recursively (n)
  (factorial-continuation (- n 1) (lambda (r) (* n r))))

这样子来定义递归函数的话似乎确实可以把任何递归函数都转换为尾递归呢?感觉可以~

--
Liutos Love Linux LaTeX Lisp Ling

我的GitHub主页:https://github.com/Liutos

Nixie O

unread,
May 21, 2012, 11:52:20 PM5/21/12
to lis...@googlegroups.com
讨论讨论。

在上面my-length尾递归版本的例子中,(+ acc 1)是在当下被求值的,并被传递给下层递归调用。
这样就不会构成一个递归下层对上层的计算依赖。

但是在上面那个CPS的例子中,每一层递归都会创建一层lambda调用,计算通过collector被搜集起来(没有在当下求值)。
我觉得这实际上是在建造一个堆上的调用栈来代替原本的递归调用栈。(个人觉得它是伪装成尾递归的啊。。。尾递归。)

对于factorial的CPS形式,其实可以不需要collector的。手下没有CL, 只有个racket。我写了另外一个CPS的版本:

(define (fact n)
  (letrec ((F (lambda (n r cont)
                     (cond ((= 0 n) r)
                              (else (cont (- n 1) (* r n) F))))))
       (cond ((= 0 n) 0)
                (else (F n 1 F)))))

letrec类似于labels,define类似于defun。

bruce li

unread,
May 21, 2012, 11:56:15 PM5/21/12
to lis...@googlegroups.com
弱弱请教下mergesort/quicksort怎么进行尾递归?


--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn

李沛旭

unread,
May 21, 2012, 11:58:51 PM5/21/12
to lis...@googlegroups.com
Ӧ��Ҳ������αװ��β�ݹ�����ֻ���ֶ�����˱������Ĺ�����
�ܶ������Ҳ�ǰѳ���ת����CPS�����԰����еĺ�����β�ݹ飬
��Ϊβ�ݹ���ʵ����goto����������ij������Ż������������кܷ��㡣

On 05/22/2012 11:52 AM, Nixie O wrote:
�������ۡ�

������my-lengthβ�ݹ�汾�������У�(+ acc 1)���ڵ��±���ֵ�ģ��������ݸ��²�ݹ���á�
����Ͳ��ṹ��һ���ݹ��²���ϲ�ļ���������

�����������Ǹ�CPS�������У�ÿһ��ݹ鶼�ᴴ��һ��lambda���ã�����ͨ��collector���Ѽ�������û���ڵ��� ��ֵ����
�Ҿ�����ʵ�������ڽ���һ�����ϵĵ���ջ������ԭ���ĵݹ����ջ��(���˾�������αװ��β�ݹ�İ�������β�ݹ顣)

����factorial��CPS��ʽ����ʵ���Բ���Ҫcollector�ġ�����û��CL�� ֻ�и�racket����д������һ��CPS�İ汾��

(define (fact n)
  (letrec ((F (lambda (n r cont)
                     (cond ((= 0 n) r)
                              (else (cont (- n 1) (* r n) F))))))
       (cond ((= 0 n) 0)
                (else (F n 1 F)))))

letrec������labels��define������defun��

On Monday, 21 May 2012 23:54:15 UTC+9, ���� wrote:
����ͨ�ĵݹ� ת����β�ݹ���û��ͨ�ÿɸ��Ƶķ����أ�

���綨����һ�������б?�ȵĺ��� (defun my-length (list) (if (null list) 0 (+ (my-length (cdr list)) 1)))�������ԣ�������ͨ�ĵݹ麯���壬ת����β�ݹ�Ҳ�� �򵥣�����


(defun my-length (list)
  (labels ((rec (acc list)
         (if (null list)
         acc
         (rec (+ acc 1)
              (cdr list)))))
    (rec 0 list)))

������һ�IJ�����Ҳ��(+ acc 1)����Ķ�acc�Ĵ��?Ӧ������ԭ���ĵݹ麯���е�``��һ��''�����г��� �ģ����ڱ��ŵ���acc�ļ����С���һ�IJ���������Ϊԭ���ĵݹ麯���е���һ�ε���ʱ�����ӣ����Կ���һ�� ������ (lambda (v) (+ v 1))������Ļ����Ϳ������Ϊ��β�ݹ�ʵ���Ͼ��ǽ�������ij�ַ�ʽ�� ��������һ�εĵݹ麯������С������ԵIJ������￴���ĸ����Ե�ʹ�����ӵķ�ʽ������쳲��������� �ĵ�n���ֵ�Ķ��壬ԭ��Ϊhttp://blog.zhaojie.me/2009/03/tail-recursion-and-continuation.html�� �Ҹ�ΪLisp������������


(defun factorial-continuation (n cont)
  (if (= 0 n)
      (funcall cont 1)
      (factorial-continuation (- n 1)
                  (lambda (r)
                (funcall cont (* n r))))))

(defun factorial-recursively (n)
  (factorial-continuation (- n 1) (lambda (r) (* n r))))

������������ݹ麯��Ļ��ƺ�ȷʵ���԰��κεݹ麯��ת��Ϊβ�ݹ��أ��о����ԡ�


--
Liutos Love Linux LaTeX Lisp Ling

�ҵ�GitHub��ҳ��https://github.com/Liutos

--
Lisp-cn(Lisp�����û���)
CLUG http://lisp.org.cn

Liutos

unread,
May 22, 2012, 1:16:16 AM5/22/12
to lis...@googlegroups.com
其实我也想到了,第二个参数所传递的匿名函数,就是把外层调用和当前调用再重新复合在一起构成一个新函数而已,确实就是用堆空间来代替函数调用时使用的栈空间而已,可能在性能上的消耗和直接使用累加器的方式是不一样的,应该会差不少,并且每一次递归都要重新构造函数,可能来得更久。

不过我觉得这里面其实隐藏了一个思路,就是如果希望避免这种情况,那么就设置一个累加器或者别的什么名字也好,它的作用就是立即调用外层的计算来计算出接下来要传递给一下次调用所需要的值。例如,这里为什么是(+ acc 1)呢?因为外层调用中原本就是(+ (my-length (cdr list)) 1),所以相当于说``当前的续延''就是一元函数(lambda (v) (+ v 1))。因为加法的可交换性,所以即使首先计算了外层的续延,也对最终结果没有影响,所以可以直接计算出这一次的结果,放入累加器,直接给下一次递归调用使用。

所以我在想,如果外层续延具有某种性质,就可以允许被调用的函数立即使用这个续延和当前的累加器值进行计算,得到接下来要用的值,直接给下一次调用使用,也就是有了通用的实现尾递归的方法:P

在 2012年5月22日 上午11:52,Nixie O <oni...@gmail.com>写道:

--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn

Liutos

unread,
May 22, 2012, 1:17:07 AM5/22/12
to lis...@googlegroups.com
CPS这么神奇?

可以说说尾递归为什么是goto吗?

在 2012年5月22日 上午11:58,李沛旭 <lip...@gmail.com>写道:
应该也不算是伪装成尾递归啦,只是手动完成了编译器的工作。
很多编译器也是把程序转换成CPS,可以把所有的函数都变成尾递归,
因为尾递归其实就是goto,所以这样的程序作优化、分析和运行很方便。


On 05/22/2012 11:52 AM, Nixie O wrote:
讨论讨论。

在上面my-length尾递归版本的例子中,(+ acc 1)是在当下被求值的,并被传递给下层递归调用。
这样就不会构成一个递归下层对上层的计算依赖。

但是在上面那个CPS的例子中,每一层递归都会创建一层lambda调用,计算通过collector被搜集起来(没有在当下 求值)。
我觉得这实际上是在建造一个堆上的调用栈来代替原本的递归调用栈。(个人觉得它是伪装成尾递归的啊。。。尾递归。)

对于factorial的CPS形式,其实可以不需要collector的。手下没有CL, 只有个racket。我写了另外一个CPS的版本:

(define (fact n)
  (letrec ((F (lambda (n r cont)
                     (cond ((= 0 n) r)
                              (else (cont (- n 1) (* r n) F))))))
       (cond ((= 0 n) 0)
                (else (F n 1 F)))))

letrec类似于labels,define类似于defun。

On Monday, 21 May 2012 23:54:15 UTC+9, 刘滔 wrote:
把普通的递归 转换成尾递归有没有通用可复制的方法呢?

例如定义了一个计算列表长度的函数 (defun my-length (list) (if (null list) 0 (+ (my-length (cdr list)) 1)))。很明显,这是普通的递归函数定义,转换成尾递归也很 简单,如下


(defun my-length (list)
  (labels ((rec (acc list)
         (if (null list)
         acc
         (rec (+ acc 1)
              (cdr list)))))
    (rec 0 list)))

本来加一的操作,也即(+ acc 1)这里的对acc的处理,应该是在原来的递归函数中的``上一层''调用中出现 的,现在被放到了acc的计算中。加一的操作可以视为原来的递归函数中的再一次调用时的续延,可以看做一个 匿名函数 (lambda (v) (+ v 1))。这样的话,就可以理解为,尾递归实际上就是将续延以某种方式保 存在了再一次的递归函数调用中。在老赵的博客那里看到的更明显地使用续延的方式来计算斐波纳契数列 的第n项的值的定义,原文为http://blog.zhaojie.me/2009/03/tail-recursion-and-continuation.html, 我改为Lisp代码后是这样的


(defun factorial-continuation (n cont)
  (if (= 0 n)
      (funcall cont 1)
      (factorial-continuation (- n 1)
                  (lambda (r)
                (funcall cont (* n r))))))

(defun factorial-recursively (n)
  (factorial-continuation (- n 1) (lambda (r) (* n r))))

这样子来定义递归函数的话似乎确实可以把任何递归函数都转换为尾递归呢?感觉可以~


--
Liutos Love Linux LaTeX Lisp Ling

我的GitHub主页:https://github.com/Liutos

--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn

--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn



--
Liutos Love Linux LaTeX Lisp Ling

我的GitHub主页:https://github.com/Liutos

Nixie O

unread,
May 22, 2012, 1:27:13 AM5/22/12
to lis...@googlegroups.com
On Tuesday, 22 May 2012 14:17:07 UTC+9, 刘滔 wrote:
CPS这么神奇?

可以说说尾递归为什么是goto吗?


因为尾递归优化中一个常见的方式就是用类似goto的方式代替函数入栈。
如果不用对函数创建stack frame的话,那和普通的jmp指令是一样的,就是goto么。

Nixie O

unread,
May 22, 2012, 1:47:09 AM5/22/12
to lis...@googlegroups.com
quicksort的递归属于树形递归。因为两个分支的计算不能同时在一个tail call position中,没有简单的尾递归。
如果非要尾递归,只有使用楼主CPS的方式,在计算一支分支的时候,将另一分支的计算作为continuation传递下去。

这有点lazy evaluation的感觉。

李沛旭

unread,
May 22, 2012, 4:25:28 AM5/22/12
to lis...@googlegroups.com
��ʵӦ����˵����ȷʵ��β�ݹ�������У�β�ݹ�����goto�ǵȼ۵ģ�
����ִ�еĽ��ʱ�俪��ջ�ͶѵĿռ俪���Լ�����side effects�ȵȡ�

On 05/22/2012 01:27 PM, Nixie O wrote:
On Tuesday, 22 May 2012 14:17:07 UTC+9, ���� wrote:
CPS��ô���棿

����˵˵β�ݹ�Ϊʲô��goto��


��Ϊβ�ݹ��Ż���һ������ķ�ʽ����������goto�ķ�ʽ���溯����ջ��
����öԺ���stack frame�Ļ����Ǻ���ͨ��jmpָ����һ��ģ�����gotoô��

 
�� 2012��5��22�� ����11:58�������� <lip...@gmail.com>д ����
Ӧ��Ҳ������αװ��β�ݹ�����ֻ���ֶ�����˱������Ĺ�����
�ܶ������Ҳ�ǰѳ���ת����CPS�����԰����еĺ�����β�ݹ飬
��Ϊβ�ݹ���ʵ����goto����������ij������Ż������������кܷ��㡣
On 05/22/2012 11:52 AM, Nixie O wrote:
�������ۡ�

������my-lengthβ�ݹ�汾�������У�(+ acc 1)���ڵ��±���ֵ�ģ��������ݸ��²�ݹ���á�
����Ͳ��ṹ��һ���ݹ��²���ϲ�ļ���������

�����������Ǹ�CPS�������У�ÿһ��ݹ鶼�ᴴ��һ��lambda���ã��� ��ͨ��collector���Ѽ�������û���ڵ��� ��ֵ����
�Ҿ�����ʵ�������ڽ���һ�����ϵĵ���ջ������ԭ���ĵݹ����ջ��(���˾�������αװ ��β�ݹ�İ�������β�ݹ顣)

����factorial��CPS��ʽ����ʵ���Բ���Ҫcollector�ġ�����û�� CL�� ֻ�и�racket����д������һ��CPS�İ汾��

(define (fact n)
  (letrec ((F (lambda (n r cont)
                     (cond ((= 0 n) r)
                              (else (cont (- n 1) (* r n) F))))))
       (cond ((= 0 n) 0)
                (else (F n 1 F)))))

letrec������labels��define������defun��

On Monday, 21 May 2012 23:54:15 UTC+9, ���� wrote:
����ͨ�ĵݹ� ת����β�ݹ���û��ͨ�ÿɸ��Ƶķ����أ�

���綨����һ�������б?�ȵĺ��� (defun my-length (list) (if (null list) 0 (+ (my-length (cdr list)) 1)))�������ԣ�������ͨ�ĵݹ麯���壬ת����β�ݹ�Ҳ�� �򵥣�����
(defun my-length (list)
  (labels ((rec (acc list)
         (if (null list)
         acc
         (rec (+ acc 1)
              (cdr list)))))
    (rec 0 list)))

������һ�IJ�����Ҳ��(+ acc 1)����Ķ�acc�Ĵ��?Ӧ������ԭ���ĵݹ麯���е�``��һ�� ''�����г��� �ģ����ڱ��ŵ���acc�ļ����С���һ�IJ���������Ϊԭ���ĵݹ������е��� һ�ε���ʱ�����ӣ����Կ���һ�� ������ (lambda (v) (+ v 1))������Ļ����Ϳ������Ϊ��β�ݹ�ʵ���Ͼ��ǽ�������ij����ʽ�� ��������һ�εĵݹ麯������С������ԵIJ������￴���ĸ����Ե�ʹ�����ӵķ�ʽ������쳲��� ������ �ĵ�n���ֵ�Ķ��壬ԭ��Ϊhttp://blog.zhaojie.me/2009/03/tail-recursion-and-continuation.html�� �Ҹ�ΪLisp������������


(defun factorial-continuation (n cont)
  (if (= 0 n)
      (funcall cont 1)
      (factorial-continuation (- n 1)
                  (lambda (r)
                (funcall cont (* n r))))))

(defun factorial-recursively (n)
  (factorial-continuation (- n 1) (lambda (r) (* n r))))

������������ݹ麯��Ļ��ƺ�ȷʵ���԰��κεݹ麯��ת��Ϊβ�ݹ��أ��о����ԡ�

--
Liutos Love Linux LaTeX Lisp Ling

�ҵ�GitHub��ҳ��https://github.com/Liutos

--
Lisp-cn(Lisp�����û���)
CLUG http://lisp.org.cn

--
Lisp-cn(Lisp�����û���)
CLUG http://lisp.org.cn



--
Liutos Love Linux LaTeX Lisp Ling

�ҵ�GitHub��ҳ��https://github.com/Liutos

Liutos

unread,
May 22, 2012, 5:59:46 AM5/22/12
to lis...@googlegroups.com
要求还真多啊,side effects都要兼顾啊汗

在 2012年5月22日 下午4:25,李沛旭 <lip...@gmail.com>写道:
其实应该是说在正确实现尾递归的语言中,尾递归必须和goto是等价的,
包括执行的结果、时间开销、栈和堆的空间开销以及其他side effects等等。


On 05/22/2012 01:27 PM, Nixie O wrote:
On Tuesday, 22 May 2012 14:17:07 UTC+9, 刘滔 wrote:
CPS这么神奇?

可以说说尾递归为什么是goto吗?


因为尾递归优化中一个常见的方式就是用类似goto的方式代替函数入栈。
如果不用对函数创建stack frame的话,那和普通的jmp指令是一样的,就是goto么。

 
在 2012年5月22日 上午11:58,李沛旭 <lip...@gmail.com>写 道:
应该也不算是伪装成尾递归啦,只是手动完成了编译器的工作。
很多编译器也是把程序转换成CPS,可以把所有的函数都变成尾递归,
因为尾递归其实就是goto,所以这样的程序作优化、分析和运行很方便。
On 05/22/2012 11:52 AM, Nixie O wrote:
讨论讨论。

在上面my-length尾递归版本的例子中,(+ acc 1)是在当下被求值的,并被传递给下层递归调用。
这样就不会构成一个递归下层对上层的计算依赖。

但是在上面那个CPS的例子中,每一层递归都会创建一层lambda调用,计 算通过collector被搜集起来(没有在当下 求值)。
我觉得这实际上是在建造一个堆上的调用栈来代替原本的递归调用栈。(个人觉得它是伪装 成尾递归的啊。。。尾递归。)

对于factorial的CPS形式,其实可以不需要collector的。手下没有 CL, 只有个racket。我写了另外一个CPS的版本:
(define (fact n)
  (letrec ((F (lambda (n r cont)
                     (cond ((= 0 n) r)
                              (else (cont (- n 1) (* r n) F))))))
       (cond ((= 0 n) 0)
                (else (F n 1 F)))))

letrec类似于labels,define类似于defun。

On Monday, 21 May 2012 23:54:15 UTC+9, 刘滔 wrote:
把普通的递归 转换成尾递归有没有通用可复制的方法呢?

例如定义了一个计算列表长度的函数 (defun my-length (list) (if (null list) 0 (+ (my-length (cdr list)) 1)))。很明显,这是普通的递归函数定义,转换成尾递归也很 简单,如下
(defun my-length (list)
  (labels ((rec (acc list)
         (if (null list)
         acc
         (rec (+ acc 1)
              (cdr list)))))
    (rec 0 list)))

本来加一的操作,也即(+ acc 1)这里的对acc的处理,应该是在原来的递归函数中的``上一层 ''调用中出现 的,现在被放到了acc的计算中。加一的操作可以视为原来的递归函数中的再 一次调用时的续延,可以看做一个 匿名函数 (lambda (v) (+ v 1))。这样的话,就可以理解为,尾递归实际上就是将续延以某种方式保 存在了再一次的递归函数调用中。在老赵的博客那里看到的更明显地使用续延的方式来计算斐波纳 契数列 的第n项的值的定义,原文为http://blog.zhaojie.me/2009/03/tail-recursion-and-continuation.html, 我改为Lisp代码后是这样的


(defun factorial-continuation (n cont)
  (if (= 0 n)
      (funcall cont 1)
      (factorial-continuation (- n 1)
                  (lambda (r)
                (funcall cont (* n r))))))

(defun factorial-recursively (n)
  (factorial-continuation (- n 1) (lambda (r) (* n r))))

这样子来定义递归函数的话似乎确实可以把任何递归函数都转换为尾递归呢?感觉可以~


--
Liutos Love Linux LaTeX Lisp Ling

我的GitHub主页:https://github.com/Liutos

--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn

--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn



--
Liutos Love Linux LaTeX Lisp Ling

我的GitHub主页:https://github.com/Liutos

--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn

--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn



--
Liutos Love Linux LaTeX Lisp Ling

我的GitHub主页:https://github.com/Liutos

李沛旭

unread,
May 22, 2012, 6:03:21 AM5/22/12
to lis...@googlegroups.com
�ҿ����õĴʲ�׼ȷ���������ָFP���side effect����ָ�Գ������л�����Ӱ�죬��ʵ��Ҫ���ǿ����ջ��

On 05/22/2012 05:59 PM, Liutos wrote:
Ҫ����డ��side effects��Ҫ��˰���

�� 2012��5��22�� ����4:25�������� <lip...@gmail.com>���
��ʵӦ����˵����ȷʵ��β�ݹ�������У�β�ݹ�����goto�ǵȼ۵ģ�
����ִ�еĽ��ʱ�俪��ջ�ͶѵĿռ俪���Լ�����side effects�ȵȡ�
On 05/22/2012 01:27 PM, Nixie O wrote:
On Tuesday, 22 May 2012 14:17:07 UTC+9, ���� wrote:
CPS��ô���棿

����˵˵β�ݹ�Ϊʲô��goto��


��Ϊβ�ݹ��Ż���һ������ķ�ʽ����������goto�ķ�ʽ���溯����ջ��
����öԺ���stack frame�Ļ����Ǻ���ͨ��jmpָ����һ��ģ�����gotoô��

 
�� 2012��5��22�� ����11:58�������� <lip...@gmail.com>д ����
Ӧ��Ҳ������αװ��β�ݹ�����ֻ���ֶ�����˱������Ĺ�����
�ܶ������Ҳ�ǰѳ���ת����CPS�����԰����еĺ�����β�ݹ飬
��Ϊβ�ݹ���ʵ����goto����������ij������Ż������������кܷ��㡣
On 05/22/2012 11:52 AM, Nixie O wrote:
�������ۡ�

������my-lengthβ�ݹ�汾�������У�(+ acc 1)���ڵ��±���ֵ�ģ��������ݸ��²�ݹ���á�
����Ͳ��ṹ��һ���ݹ��²���ϲ�ļ���������

�����������Ǹ�CPS�������У�ÿһ��ݹ鶼�ᴴ��һ��lambda���ã��� ��ͨ��collector���Ѽ�������û���ڵ��� ��ֵ����
�Ҿ�����ʵ�������ڽ���һ�����ϵĵ���ջ������ԭ���ĵݹ����ջ��(���˾� ������αװ ��β�ݹ�İ�������β�ݹ顣)

����factorial��CPS��ʽ����ʵ���Բ���Ҫcollector�ġ��� ��û�� CL�� ֻ�и�racket����д������һ��CPS�İ汾��
(define (fact n)
  (letrec ((F (lambda (n r cont)
                     (cond ((= 0 n) r)
                              (else (cont (- n 1) (* r n) F))))))
       (cond ((= 0 n) 0)
                (else (F n 1 F)))))

letrec������labels��define������defun��

On Monday, 21 May 2012 23:54:15 UTC+9, ���� wrote:
����ͨ�ĵݹ� ת����β�ݹ���û��ͨ�ÿɸ��Ƶķ����أ�

���綨����һ�������б?�ȵĺ��� (defun my-length (list) (if (null list) 0 (+ (my-length (cdr list)) 1)))�������ԣ�������ͨ�ĵݹ麯���壬ת����β�ݹ�Ҳ�� �򵥣�����
(defun my-length (list)
  (labels ((rec (acc list)
         (if (null list)
         acc
         (rec (+ acc 1)
              (cdr list)))))
    (rec 0 list)))

������һ�IJ�����Ҳ��(+ acc 1)����Ķ�acc�Ĵ��?Ӧ������ԭ���ĵݹ麯���е�``��һ�� ''�����г��� �ģ����ڱ��ŵ���acc�ļ����С���һ�IJ���������Ϊԭ���ĵݹ麯���е��� һ�ε���ʱ�����ӣ����Կ���һ�� ������ (lambda (v) (+ v 1))������Ļ����Ϳ������Ϊ��β�ݹ�ʵ���Ͼ��ǽ�������ij�ַ�ʽ�� ��������һ�εĵݹ麯������С������ԵIJ������￴���ĸ����Ե�ʹ�����ӵķ�ʽ������ 쳲��� ������ �ĵ�n���ֵ�Ķ��壬ԭ��Ϊhttp://blog.zhaojie.me/2009/03/tail-recursion-and-continuation.html�� �Ҹ�ΪLisp������������


(defun factorial-continuation (n cont)
  (if (= 0 n)
      (funcall cont 1)
      (factorial-continuation (- n 1)
                  (lambda (r)
                (funcall cont (* n r))))))

(defun factorial-recursively (n)
  (factorial-continuation (- n 1) (lambda (r) (* n r))))

������������ݹ麯��Ļ��ƺ�ȷʵ���԰��κεݹ麯��ת��Ϊβ�ݹ��أ� �о����ԡ�

--
Liutos Love Linux LaTeX Lisp Ling

�ҵ�GitHub��ҳ��https://github.com/Liutos

--
Lisp-cn(Lisp�����û���)
CLUG http://lisp.org.cn

--
Lisp-cn(Lisp�����û���)
CLUG http://lisp.org.cn



--
Liutos Love Linux LaTeX Lisp Ling

�ҵ�GitHub��ҳ��https://github.com/Liutos

--
Lisp-cn(Lisp�����û���)
CLUG http://lisp.org.cn

--
Lisp-cn(Lisp�����û���)
CLUG http://lisp.org.cn



--
Liutos Love Linux LaTeX Lisp Ling

Fei Rao

unread,
Jun 4, 2012, 11:20:20 PM6/4/12
to lis...@googlegroups.com
其实SICP里面写得还算清楚:要把普通递归转为尾递归(及迭代),可以先尝试找出循环不变式,然后将该不变式作为函数参数,使得每次计算都在计算参数时候做完。看看do就知道了

不是所有的递归都可以写成尾递归形式,因为如果没有循环不变式,那么基本上就无法用尾递归,例如杨辉三角。

Liutos

unread,
Jun 5, 2012, 12:40:18 AM6/5/12
to lis...@googlegroups.com
哟,还有这么个说法?!再去折腾一下看看有没有规律:P

--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn

Nala Ginrut

unread,
Jun 5, 2012, 2:14:57 AM6/5/12
to lis...@googlegroups.com
能用尾递归解决的问题都算是比较简单的问题,不过一般工程性问题都可以满足了,只是科学计算方面麻烦点

2012/6/5 Liutos <mat.l...@gmail.com>:

Fei Rao

unread,
Jun 5, 2012, 2:44:17 AM6/5/12
to lis...@googlegroups.com
我先列几个例子:
计算x^n
;; 普通递归
    (define (exp x n)
  1. (if (= n 0)
  2.     1
  3.     (* x (exp x (- n 1)))))
  4. ;; 尾递归。循环不变式:x^i = x^(i-1) * x
    1. (define (exp-iter x n)
    2.   (define (iter x n r)
    3.     (if (= n 0)
    4.         r
    5.         (iter x (- n 1) (* r x))))
    6.   (iter x n 1))
    7. ;; 快速尾递归,时间复杂度O(logn),循环不变式:x^2i = x^(2i - 2) * x^2
    8. (define (fast-exp-iter x n)
        (define (iter x n r)
          (cond ((= n 0) r)
                ((even? n) (iter (* x x) (/ n 2) r)) ;; 循环不变式:(* (* x x) r) = r*x^2
                (else (iter x (- n 1) (* r x)))))  ;; 循环不变式:(* x (* r x)) = r*x^2 
        (iter x n 1))

    9. 求f(n),其中, 当n<3时,f(n)=n;否则,f(n) = f(n-1)+2f(n-2)+3f(n-3)。
  1. (define (f-i n) 
  2.   (let iter ((fn 4) (fn-1 2) (fn-2 1) (fn-3 0) (i n)) 
  3.     (cond ((< n 3) n) 
  4.           ((= i 3) fn) 
  5.           (else 
  6.            (iter (+ fn (* 2 fn-1) (* 3 fn-2)) ;; 循环不变式:f(i+1) = f(i) + 2f(i-2) + 3f(i-2)
  7.                  fn 
  8.                  fn-
  9.                  fn-
  10.                  (- i 1))))))

Liutos

unread,
Jun 5, 2012, 3:08:39 AM6/5/12
to lis...@googlegroups.com
我有几个问题想问,

第一、在第一个例子中,普通尾递归的循环不变式是x^i = x * x^(i-1),那么如何根据循环不变式来推知递归的base case是(= n 0)呢?
第二、如何根据循环不变式推知内部的iter函数所需要的参数为x、n和r呢?

Fei Rao

unread,
Jun 5, 2012, 3:27:28 AM6/5/12
to lis...@googlegroups.com


On Tuesday, June 5, 2012 3:08:39 PM UTC+8, 刘滔 wrote:
我有几个问题想问,

第一、在第一个例子中,普通尾递归的循环不变式是x^i = x * x^(i-1),那么如何根据循环不变式来推知递归的base case是(= n 0)呢?
这个base case是在获取循环不变式之前就确定的,其中base case有时候对于确定loop invariant很重要
 
第二、如何根据循环不变式推知内部的iter函数所需要的参数为x、n和r呢?
这个基本上就是参数、集合以及结果。如果还有疑问,建议看看do,尝试用do来解决一个问题,这样同时就确定了需要多少个参数了

Pascal J. Bourguignon

unread,
Jun 5, 2012, 1:59:21 AM6/5/12
to lis...@googlegroups.com
Fei Rao <rao...@gmail.com> writes:

> 其实SICP里面写得还算清楚:要把普通递归转为尾递归(及迭代),可以先尝试
> 找出循环不变式,然后将该不变式作为函数参数,使得每次计算都在计算参数时
> 候做完。看看do就知道了
>
> 不是所有的递归都可以写成尾递归形式,因为如果没有循环不变式,那么基本上
> 就无法用尾递归,例如杨辉三角。


如果递归占地面积只有一维,那么我们可以随时变换递归递归非终端。

例如,这里是帕斯卡三角形与非递归的终端:


(defun 杨惠线 (line)
(cond
((endp line)
'(1))
((endp (rest line))
line)
(t
(cons (+ (first line) (second line))
(杨惠线 (rest line))))))


这里是你如何能变换一个递归,使用“电池”:

(defun 杨惠线尾 (line new-line)
(cond
((endp line)
(cons 1 new-line))
((endp (rest line))
(cons 1 new-line))
(t
(杨惠线尾 (rest line)
(cons (+ (first line) (second line))
new-line)))))


(杨惠线尾 '(1 3 3 1) '(1))
--> (1 4 6 4 1)


(defun 杨辉三角尾 (n 三角)
(if (zerop n)
(reverse 三角)
(杨辉三角尾 (1- n) (cons (杨惠线尾 (first 三角) '(1)) 三角))))

(defun 杨辉三角 (n)
(杨辉三角尾 n '((1))))

(map nil 'print (杨辉三角 10))

(1)
(1 1)
(1 2 1)
(1 3 3 1)
(1 4 6 4 1)
(1 5 10 10 5 1)
(1 6 15 20 15 6 1)
(1 7 21 35 35 21 7 1)
(1 8 28 56 70 56 28 8 1)
(1 9 36 84 126 126 84 36 9 1)
(1 10 45 120 210 252 210 120 45 10 1)
--> NIL

谢谢translate.google.com

--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

Liutos

unread,
Jun 5, 2012, 10:19:00 AM6/5/12
to lis...@googlegroups.com
楼上果然是翻译,辛苦你了~

--
Lisp-cn(Lisp中文用户组)
CLUG http://lisp.org.cn

Liutos

unread,
Jun 5, 2012, 10:25:00 AM6/5/12
to lis...@googlegroups.com
嗯,base case那个发现不需要问的,笨了。不过根据你回答的第二条,我觉得既然既然要变换普通递归为尾递归要重新归结到do这样的迭代过程上去,那么也就是说其实变换之前就已经利用迭代的结构来实现了一遍等价的功能。其实我更想知道的是,循环不变式x^i = x * x^(i-1)如何能够自动地决定出一个函数的参数列表以及递归时需要进行的运算。例如,存在某种方法,可以直接告诉你:“哦,你要定义一个函数叫做fn,它的参数为x、n和r。而当进行递归调用时则进行运算x、(- n 1)和(* r x)并相应地填充参数列表。”

如果是先利用迭代的思路来做的,那么其实我觉得这样来实现尾递归依靠的,是``经验''。

Jay Xu

unread,
Jun 5, 2012, 9:09:59 PM6/5/12
to lis...@googlegroups.com
这翻译实在有些龊。。。
> --
> Lisp-cn(Lisp中文用户组)
> CLUG http://lisp.org.cn

--
Jay Xu

Fei Rao

unread,
Jun 5, 2012, 9:22:06 PM6/5/12
to lis...@googlegroups.com
我确实“经验主义”了,不过我也没找到一种通用的方法来决定参数

Liutos

unread,
Jun 5, 2012, 9:49:41 PM6/5/12
to lis...@googlegroups.com
要是有通用的方法就好了T_T。我觉得循环不变式应该是个不错的切入点呢,改天折腾一下

Nixie O

unread,
Jun 5, 2012, 11:24:28 PM6/5/12
to lis...@googlegroups.com
递归不变式是可以变换的,所以尾递归可以写成很多不同版本。
这样参数就更难确定了。

拜访了你的博客,不错不错。

Jay Xu

unread,
Jun 6, 2012, 10:05:20 AM6/6/12
to lis...@googlegroups.com
没学过循环不变式的弱弱的问一下,树形递归是否可以通过类似的方法转化为尾递归呢?
自己试了下,找不到思路。
> --
> Lisp-cn(Lisp中文用户组)
> CLUG http://lisp.org.cn

--
Jay Xu

Liutos

unread,
Jun 6, 2012, 9:43:31 PM6/6/12
to lis...@googlegroups.com
参考一楼给出的链接中老赵的例子吧,思路是自己构造续延来把左树或者右树的递归容纳进去,然后传给下一次递归调用。

Nixie O

unread,
Jun 7, 2012, 11:27:11 PM6/7/12
to lis...@googlegroups.com
(define copy-tree
  (lambda (tree)
    (letrec ((cp (lambda (t col)
                   (cond
                         ((null? t) (col t))
                         ((not (or (pair? (car t))
                                     (null? (car t))))
                          (cp (cdr t)
                              (lambda (st)
                                (col (cons (car t) st)))))
                         (else
                          (cp (car t)
                              (lambda (a-st)
                                (cp (cdr t)
                                    (lambda (d-st)
                                      (col (cons a-st d-st)))))))))))
      (cp tree identity))))

树形递归的关键在else分支里。思路是将本来并行的递归线性化。
Reply all
Reply to author
Forward
0 new messages