Scheme中的递归方法

Question

我在 Scheme 中有一个（理论上）简单的方法，它必须使用递归。问题是我似乎无法弄清楚递归部分......我有一个过程接受 'pointer' 和任意多个参数，我需要将参数一个一个地传递给另一个方法。这是我到目前为止得到的：

(define (push-elements ptr . args)
    (define (push-all ptr list)
        (if (null? list)
            '()
            (ptr 'push-elements (car list))))
     (push-all ptr list))

我知道这里没有递归，但我不明白应该把 it/how 放在哪里。思路清晰，里面'push-all'需要调用：

(push-all ptr (cdr list))

如果有人能帮助我（我将非常感谢解释如何进行这种递归方法），那就太好了。

Answer 1

考虑基本情况和每个增量情况会很有帮助。如果您尝试 push-all 到堆栈上但没有任何项目，结果应该是什么？只是堆栈。如果您尝试 push-all 到堆栈上并且您有多个项目，结果是什么？好吧，首先你要把第一个项目推到堆栈上，给你一个新的堆栈。然后你可以 push-all rest 的项目到那个堆栈：

(define (push-all stack items)
  (if (null? items)
      stack
      (let ((new-stack (cons (car items) stack))
            (remaining-items (cdr items)))
        (push-all new-stack remaining-items))))

(display (push-all '(1 2) '(a b c)))
;=> (c b a 1 2)

现在，您的原始版本是可变的。也就是说，它接受任意数量（好吧，大于零）的参数，因为它是点分的 arglist。很好，但这确实意味着您需要在设置递归调用时使用 apply：

(define (push-all stack . items)
  (if (null? items)
      stack
      (let ((new-stack (cons (car items) stack))
            (remaining-items (cdr items)))
        (apply push-all new-stack remaining-items))))

(display (push-all '(1 2) 'a 'b 'c))
;=> (c b a 1 2)

Answer 2

基本上，您正在实施 for-each 的变体，它类似于 map 只是为了副作用：

(define (for-each procedure lst)
  (let loop ((lst lst))
    (if (null? lst)        
        'undefined-value
        (begin
          (procedure (car lst))
          (loop (cdr lst))))))

(for-each display (list 1 2 3 4)) ; prints 1234

但是您希望能够将值指定为参数，因此您需要将 lst 更改为剩余参数：

(define (for-each-arg procedure . lst) ; changed to dotted list / rest here
  (let loop ((lst lst))
    (if (null? lst)        
        'undefined-value
        (begin
          (procedure (car lst))
          (loop (cdr lst))))))

(for-each-arg display 1 2 3 4) ; prints 1234

如果你想要一个更实用的方法，你确实在制作地图或折叠。也许左折会更好：

(define (fold-args join init . lst)
  (let loop ((acc init) (lst lst))
    (if (null? lst)
        acc
        (loop (join (car lst) acc) (cdr lst)))))

(fold-args cons '() 1 2 3 4) ; ==> (4 3 2 1)

您实际上可以这样实现 for-each-arg：

(define (for-each-arg procedure . lst)
  (apply fold-args 
         (lambda (x acc) 
           (procedure x) 
           'undefined) 
         'undefined 
         lst))

(for-each-arg display 1 2 3 4) ; => undefined-value; prints 1234

Scheme中的递归方法

Recursive method in Scheme

list

recursion

scheme

message-passing

r5rs