1

编辑：谢谢大家。我是这种语言的新手（两天前才开始使用它），所以这就是我不熟悉 conds 的原因。如果我有时间，我可能会重写它，但我只是想确保我的基本逻辑是正确的。再次感谢！

我的任务是创建一个尾递归函数，它从列表中删除第 n 个元素，1 <= n <= listlength，只有两个参数，列表 x 和元素 n。因此，(remove 1 '(abcd)) 将返回 (bcd)。我已经写了以下内容，并希望确信它确实是尾递归的。我唯一不清楚的是递归调用是否可以嵌套在 IF 语句中。

(define (remove n x)
  ; if n is 1, just return the cdr 
  (if (and (not (list? (car x))) (= n 1))
     (cdr x)
     ; if the car is not a list, make it one, and call recursively
     (if (not (list? (car x)))
        (remove (- n 1) (cons (list (car x)) (cdr x)))
        ; if n !=1, insert the cadr into the list at the car.
        ; Else, append the list at the car with the cddr
        (if (not(= n 1))
           (remove (- n 1) (cons (append (car x) (list(cadr x))) (cddr x)))
           (append (car x) (cddr x))))))
4

2 回答 2

2

是的，该过程是尾递归的，这意味着：无论在何处执行递归调用，它都是在该特定执行分支中发生的最后一件事，在递归返回后无事可做 - 因此，我们说递归调用是在尾部位置。

cond如果我们使用而不是嵌套s重写过程，可以清楚地看到这一点if，在这里您将看到每个执行分支都会导致基本情况或递归情况，并且所有递归调用都位于尾部位置：

(define (remove n x)
         ; base case #1
  (cond ((and (not (list? (car x))) (= n 1))
         ; return from base case, it's not recursive
         (cdr x))
         ; recursive case #1
        ((not (list? (car x)))
         ; recursive call is in tail position
         (remove (- n 1) (cons (list (car x)) (cdr x))))
         ; recursive case #2
        ((not (= n 1))
         ; recursive call is in tail position
         (remove (- n 1) (cons (append (car x) (list(cadr x))) (cddr x))))
         ; base case #2
        (else
         ; return from base case, it's not recursive
         (append (car x) (cddr x)))))

有关为什么if特殊形式的后件/替代部分可以被视为尾递归的更技术性解释，请查看关于算法语言方案的修订^7报告的当前草案的第 3.5 节 - 语言规范，这里是一个指向 pdf 文件的链接（本质上，同样的考虑也适用于 R5RS，只是它们在 R7RS 中有更详细的解释）。尤其是：

如果以下表达式之一处于尾部上下文中，则显示为 ⟨tail expression⟩ 的子表达式处于尾部上下文中

...

(if ⟨expression⟩ ⟨tail expression⟩ ⟨tail expression⟩)

(if ⟨expression⟩ ⟨tail expression⟩)

于 2013-03-26T23:15:51.043 回答
0

这是句法形式的尾递归位置的 Scheme 规范： 在此处输入图像描述

于 2013-03-27T00:41:05.933 回答