algorithm - 这个递归函数是迭代的吗？

Question

我正在观看 sicp 讲座，在视频 1b 中，sussman 将算法 1 称为迭代。他说方法2是递归的。据我了解，两者都是递归算法。我怎样才能最好地想到方法1？作为迭代递归算法？

https://www.youtube.com/watch?v=dlbMuv-jix8

方法1 - 时间复杂度为o(x)，空间复杂度为o(1)

 (define (+ x y)
        (if (= x 0)
            y
            (+ (-1+ x) (1+ y))))

方法2 - 时间补数为o(x)，空间补数为o(x)

(define (+ x y)
    (if (= x 0)
        y
        (1+ (+ (-1+ x) y))))

Answer 1

您的第一个示例是尾递归，因此是迭代的，第二个示例会增加堆栈，但不是。

在 SICP 视频中，他们将尾递归过程称为迭代。他们倾向于将非迭代过程称为递归，即使递归是Scheme 中唯一的循环机制。 (像 do 这样的东西只是尾递归过程调用的语法糖。) 与尾递归过程相反的过程没有一个好名字。

尽管如此，Sussman 既是《Scheme》的作者之一，又是《SICP》一书的作者之一，因此在所有奇才中他是最伟大的。该视频来自 80 年代，当时的报道是 R3RS。即使他们使用的语言是旧版本的方案，它与当今最常用的方案报告 R5RS 相差不远。