这个过程是递归的还是迭代的(长尾递归)

Question

下面的代码用于实现一个名为"build-list"的内置函数:

(define (my-build-list-book n f)
 (define (builder k)
   (cond [(= n k) empty]
         [else (cons (f k) (builder (add1 k)))]))
  (builder 0))
(my-build-list-book 10 add1)
>> '(1 2 3 4 5 6 7 8 9 10)

这是迭代过程的递归定义还是递归过程的递归定义?

Answer 1

builder是递归的，因为它调用自己:(builder (add1 k))

它不是尾部递归的，因为对自身的调用不是在原始过程返回值的地方进行的。它使用递归调用的结果作为cons的参数，而不是返回值。

尾部递归的变体将以如下方式结束:

[else (builder ...)]

将这样的函数转换为尾递归通常需要添加一个额外的参数，该参数包含由基准情况返回的累积结果。

(define (my-build-list-book n f)
  (define (builder k result)
    (cond [(= n k) result]
          [else (builder (add1 k) (cons (f k) result))]))
  (builder 0 '()))

我不知道你说的"长尾递归"是什么意思，我从来没有听说过这个短语，我在谷歌上也找不到。