给定方案中的递归函数，如何将该函数更改为尾递归，然后如何使用流实现它？以这种方式更改任何功能时，是否有遵循的模式和规则？
以这个函数为例，它从 2-m 创建一个数字列表（这不是尾递归吗？）
代码：
(define listupto
(lambda (m)
(if (= m 2)
'(2)
(append (listupto (- m 1)) (list m)))))
user1311286
问问题
384 次
4 回答
4
我将从解释你的例子开始。它绝对不是尾递归。想想这个函数是如何执行的。每次追加时，您必须先返回并进行递归调用，直到遇到基本情况，然后再向上拉。
这就是你的功能的踪迹：
(listupto 4)
| (append (listupto(3)) '4)
|| (append (append (listupto(2)) '(3)) '(4))
||| (append (append '(2) '(3)) '(4))
|| (append '(2 3) '(4))
| '(2 3 4)
'(2 3 4)
请注意您看到的 V 型模式拉入然后拉出递归调用。尾递归的目标是将所有调用构建在一起，并且只执行一次。您需要做的是与您的函数一起传递一个累加器，这样当您的函数到达基本情况时，您只能进行一个追加。
这是您的函数的尾递归版本：
(define listupto-tail
(lambda (m)
(listupto m '())))
# Now with the new accumulator parameter!
(define listupto
(lambda (m accu)
(if (= m 2)
(append '(2) accu)
(listupto (- m 1) (append (list m) accu)))))
如果我们看到这个踪迹，它看起来像这样：
(listupto 4)
| (listupto (3) '(4)) # m appended with the accu, which is the empty list currently
|| (listupto (2) '(3 4)) # m appended with accu, which is now a list with 4
||| (append '(2) '(3 4))
'(2 3 4)
注意模式是如何不同的，我们不必遍历递归调用。这为我们节省了无意义的处决。尾递归可能是一个难以掌握的概念，我建议看看这里。第 5 章中有一些有用的部分。
于 2012-07-25T16:29:03.413 回答
3
通常要切换到尾递归形式，您需要转换代码，以便它采用累加器参数来构建结果并用作最终返回值。这通常是您的主要功能也委托的辅助功能。
某种形式的东西：
(define listupto
(lambda (m)
(listupto-helper m '())))
(define listupto-helper
(lambda (m l)
(if (= m 2)
(append '(2) l)
(listupto-helper (- m 1) (append (list m) l)))))
正如评论所指出的，辅助函数可以用一个命名的 let 替换，这显然（还没有做太多/足够的方案！）更惯用（并且正如评论所暗示cons的那样，比创建列表和附加要好得多。
(define listupto
(lambda (n)
(let loop ((m n) (l '()))
(if (= m 2)
(append '(2) l)
(loop (- m 1) (cons m l))))))
于 2012-07-25T16:22:58.873 回答
0
您还询问有关流的问题。您可以在此处或此处找到使用的 SICP 样式流，其中定义了from-By流构建器：
;;;; Stream Implementation
(define (head s) (car s))
(define (tail s) ((cdr s)))
(define-syntax s-cons
(syntax-rules ()
((s-cons h t) (cons h (lambda () t)))))
;;;; Stream Utility Functions
(define (from-By x s)
(s-cons x (from-By (+ x s) s)))
此类流的创建依赖于宏，并且必须通过特殊方式访问它们：
(define (take n s)
(cond ; avoid needless tail forcing for n == 1 !
((= n 1) (list (head s))) ; head is already forced
((> n 1) (cons (head s) (take (- n 1) (tail s))))
(else '())))
(define (drop n s)
(cond
((> n 0) (drop (- n 1) (tail s)))
(else s)))
但它们不是持久的，即在每次访问时重新计算它们take。drop使流持久化的一种方法是通过手术改变最后一个访问的 cons 单元的尾部关闭：
(1 . <closure>)
(1 . (2 . <closure>))
....
像这样：
(define (make-stream next this state)
(let ((tcell (list (this state)))) ; tail sentinel cons cell
(letrec ((g (lambda ()
(set! state (next state))
(set-cdr! tcell (cons (this state) g))
(set! tcell (cdr tcell))
tcell)))
(set-cdr! tcell g)
tcell)))
(define (head s) (car s))
(define (tail s)
(if (or (pair? (cdr s))
(null? (cdr s)))
(cdr s)
((cdr s))))
我们现在可以像这样使用它
(define a (make-stream (lambda (i) (+ i 1)) (lambda (i) i) 1))
;Value: a
a
;Value 13: (1 . #[compound-procedure 14])
(take 3 a)
;Value 15: (1 2 3)
a
;Value 13: (1 2 3 . #[compound-procedure 14])
(define b (drop 4 a))
;Value: b
b
;Value 16: (5 . #[compound-procedure 14])
a
;Value 13: (1 2 3 4 5 . #[compound-procedure 14])
(take 4 a)
;Value 17: (1 2 3 4)
a
;Value 13: (1 2 3 4 5 . #[compound-procedure 14])
现在，(make-stream (lambda (i) (list (cadr i) (+ (car i) (cadr i)))) car (list 0 1))定义什么？
更新：在Daniel Friedman的 1994 年幻灯片“The Joys of Scheme, Cont'd”中，我们发现这些“记忆流”（在那里被称为）的更简单实现，使tail函数本身将强制流存储在尾部哨兵中，作为
(define (tail s)
(if (or (pair? (cdr s))
(null? (cdr s)))
(cdr s)
(let ((n ((cdr s))))
(set-cdr! s n)
(cdr s))))
;; can be used as e.g. (https://ideone.com/v6pzDt)
(define fibs
(let next-fib ((a 0) (b 1))
(s-cons a (next-fib b (+ a b)))))
于 2012-07-28T10:11:48.953 回答
0
这是一个尾递归形式 -
(define (listupto n)
(let run
((m 0)
(return identity))
(if (> m n)
(return null)
(run (add1 m)
(lambda (r) (return (cons m r)))))))
(listupto 9)
; '(0 1 2 3 4 5 6 7 8 9)
这里是流——
(define (listupto n)
(let run
((m 0))
(if (> m n)
empty-stream
(stream-cons m
(run (add1 m))))))
(stream->list (listupto 9))
; '(0 1 2 3 4 5 6 7 8 9)
于 2020-08-15T20:01:33.553 回答