尾递归理解

Question

我想知道是否有人可以指导我完成尾递归。我有我在 Racket 中制作的这个程序，我想简单解释一下我应该采取哪些步骤来利用尾递归形式的东西。

Racket中的代码如下，

;SQUARE LIST FUNCTION
(define (square-list lst)
  (cond
    [(empty? lst) 0]
    [else (map (lambda (i)
                 (* i i)) lst)]))

或更好地定义为。

(define (square-list lst)
  (for-each (lambda (i)
    (printf "Iteration: ~a\n" (* i i)))lst))

所以我真的只想知道：

我应该如何将此过程更改为尾递归过程？

Answer 1

从某种意义上说，您的两个示例都是 tail call optimized，解释器可以查看它并看到在第一种情况下 cond 始终作为此函数调用的最后一个表达式执行。这意味着它不保持堆栈。在您的第二个示例中，它可以告诉您 for-each 语句将始终最后执行。

出于教学目的，请查看以下函数：

(define (square-list ls)
    (if (empty? ls)
      '()
      (let ((first-square (* (car ls) (car ls))))
          (cons first-square (square-list (cdr ls)))))

在此函数中，您将计算第一个元素的平方。那么整个列表的平方的结果就是这个平方，cons'd 到递归调用函数的前面，对列表的其余部分执行相同的操作。

重点是在这种情况下，解释器必须记住first-square值，然后计算其余的方块，最后创建一个列表他们。记住部分是使函数非尾递归的部分。

所以它基本上可以归结为通过构建输出并将中间结果连续调用传递给函数来帮助您的解释器尽可能少地记住。那么我们该怎么做呢？很简单，将平方值传递给递归调用并确保递归调用是函数体中的最后一条语句。

(define (square-list ls squares)
    (if (empty? ls)
      squares
      (let ((first-square (* (car ls) (car ls))))
          (square-list (cdr ls) (cons first-square squares)))

我们在这里所做的是在函数调用中创建输出（方块列表）。这意味着每个递归调用都会得到一个已经平方值的列表。所以在正文中，我们简单地获取 "unsquared" 列表的值并将该值转换为平方值列表。

所以调用这个函数很简单：

(square-list '(1 2 3) '())

在每次迭代中，我们将从输入列表中获取第一个值，将其平方并将其转换为输出列表。

（注意：这将产生反向平方列表）

REPL 中的示例

Welcome to DrRacket, version 5.3.6 [3m].
Language: racket; memory limit: 128 MB.
> (define (square-list ls squares)
    (if (empty? ls)
      squares
      (let ((first-square (* (car ls) (car ls))))
          (square-list (cdr ls) (cons first-square squares)))))
> (square-list '(1 2 3) '())
'(9 4 1)
>

尾递归理解

Tail Recursion Understanding

recursion

scheme

racket