迭代函数可以调用自身吗？

Question

观看下面的麻省理工学院 6.001 课程视频时，28:00 讲师将此算法标记为迭代。但是，在 30.27，他说这个算法和实际的 "recursive" 算法都是递归的。该函数正在使用基本情况调用自身，那么这次迭代如何？

https://www.youtube.com/watch?v=dlbMuv-jix8&list=PLE18841CABEA24090&index=2

private int iterativeSum(int x, int y)
{
    System.out.println("x "+x+" y "+y);
    if(x == 0)
    {
        return y;
    }
    return iterativeSum(--x, ++y);
}

Answer 1

讲师似乎更感兴趣的是它是如何执行的，而不是代码是如何编写的。这两者之间有很大的区别，但那完全是另一回事（但值得注意的是，例如，某些语言会将递归编译为迭代）。

在这种情况下，它是迭代当您将整个状态放在一个地方并重复处理那一条数据时。它是递归当你有一堆状态并添加到堆栈，然后最终将堆栈折叠回一个答案。

在 31:00 的讲师示例中，他将此表示为迭代，即一张纸保存了迄今为止完成的工作的全部状态，任何人都可以拿走它并最终得出最终答案。

在 32:20 的递归示例中，Joe 对问题有自己的笔记，并且只传递了关于问题的一部分的笔记。然后 Harry 有足够的信息用于他的问题部分，但是整个问题仍然需要 Joe 在从 Harry 那里得到结果时保留他自己的信息来处理 Harry 的结果。

你有一整堆人，随着更多人的加入，直到其中一个人有一个简单到可以自己解决的问题，并且他可以 return 他的答案马上，这意味着倒数第二个人现在有一个更简单的问题，现在可以 return his 回答，依此类推，直到整个人堆回到最后（第一）个人谁再给出最终答案。

Answer 2

我认为这是基于 SICP 中的定义。这里是 the relevant section. 简而言之，递归函数可以生成迭代 process 如果递归调用在尾部位置： none 的局部变量的当前值需要记住并且它们的 space 可以被清除/重用（使用 LISP 更容易看到一切都是表达式，并且可以看到表达式的大小在迭代过程中如何不增长）。

相比之下，递归过程在递归调用完成后还没有完成。例如这个函数

private int recursiveSum(int x, int y)
{
    if(x == 0)
    {
        return y;
    }
    return ++(recursiveSum(--x, y));
}

会生成递归过程，因为还需要做额外的工作(++())。

编译器是否会真正实现尾调用优化 (TCO) 是另一回事。 AFAIK，迄今为止 JVM 不支持它。在尾部位置调用自身的函数通常易于优化（作为循环）。当一个函数调用另一个函数，另一个函数调用第一个函数时，困难就来了，等等。

Answer 3

在函数调用自身的意义上，它是递归的。但是，它有一个重要的属性，即调用的结果仅取决于另一个函数调用的结果；不需要当前堆栈中的任何值。结果由

提供

return iterativeSum(--x, ++y);

不是来自

return iterativeSum(--x, ++y) + x;

这将需要 "coming back" 来自递归调用，对结果做一些事情，然后返回它。因为结果不需要当前栈帧的任何内容，所以实现（在某些语言中，取决于语义）可以消除或重用当前栈帧。这称为 尾调用消除，它在某些语言中是强制性的，例如 Scheme。这就是为什么该算法的 Scheme 实现本质上是迭代的：它不需要无限数量的堆栈 space.

在Scheme中，尾调用消除意味着实现本质上是下面的，其中iterativeSumDriver是一种蹦床，或者对[提供的结果的迭代驱动程序=33=]内部迭代求和.

public class IterativeSummer {
    /**
     * Returns a sum, computed iteratively.
     *
     * @param x the augend
     * @param y the addend
     * @return the sum of the augend and addend
     */
    public int iterativeSumDriver(int x, int y) {
        int[] state = new int[] { x, y };
        while (state.length == 2) {
            state = iterativeSumInternal(state[0], state[1]);
        }
        return state[0];
    }

    /**
     * Returns the new computation state of a iterative sum
     * computation.  If x is 0, then returns an array of just y.
     * Otherwise, returns an an array of x-1 and y+1.
     *
     * @param x the augend
     * @param y the addend
     * @return the next interal state
     */
    int[] iterativeSumInternal(int x, int y) {
        if (x == 0) {
            return new int[] { y };
        }
        else {
            return new int[] { x-1, y+1 };
        }
    }

    public static void main(String[] args) {
        int x = 5;
        int y = 6;
        int sum = new IterativeSummer().iterativeSumDriver(x,y);
        System.out.println(String.format("%d + %d = %d", x, y, sum));
    }
}

一个合适的蹦床

作为，一个真正的蹦床并不真正了解计算中使用的状态；它只需要调用一些东西，直到返回一个不可调用的东西。这是一个可以做到这一点的版本。

public class Trampoline {
    /**
     * State of a computation for a trampoline.
     * 
     * @param <T> the type of value
     */
    public interface TrampolineState<T> {
        /**
         * Returns whether the state is a finished state.
         * 
         * @return whether the state is a finshed state
         */
        boolean isFinished();

        /**
         * Returns the value, if this state is finished.
         * 
         * @return the value
         * @throws IllegalStateException if the state is not finished
         */
        T getValue() throws IllegalStateException;

        /**
         * Returns the next state, if this state is not finished.
         * 
         * @return the next state
         * @throws IllegalStateException if the state is finished
         */
        TrampolineState<T> getNext() throws IllegalStateException;
    }

    /**
     * Executes a trampolined state and its successors until a finished state is
     * reached, and then returns the value of the finished state.
     * 
     * @param state the state
     * @return the value
     */
    public <T> T trampoline(TrampolineState<T> state) {
        while (!state.isFinished()) {
            state = state.getNext();
        }
        return state.getValue();
    }

    /**
     * Returns the state for for sum computation. 
     * 
     * @param x the augend
     * @param y the addend
     * @return the state
     */
    private TrampolineState<Integer> getSumTrampolineState(int x, int y) {
        return new TrampolineState<Integer>() {
            @Override
            public boolean isFinished() {
                return x == 0;
            }

            @Override
            public Integer getValue() {
                if (!isFinished()) {
                    throw new IllegalStateException();
                }
                return y;
            }

            @Override
            public TrampolineState<Integer> getNext() {
                if (isFinished()) {
                    throw new IllegalStateException();
                }
                return getSumTrampolineState(x - 1, y + 1);
            }
        };
    }

    /**
     * Returns a sum, computed by a trampolined computation.
     * 
     * @param x the augend
     * @param y the addend
     * @return the sum
     */
    public int sum(int x, int y) {
        return trampoline(getSumTrampolineState(x, y));
    }
}

另请参阅：

How do I jump out of a function in Lisp?
What is a trampoline function?

Answer 4

这里使用的 "recursive" 这个词有两种不同的含义。一个是语法上的——任何调用自身的函数在语法上（即语法方面）都是递归的。

另一个是关于由给定代码片段编码的计算过程的基本行为——它是否在常量堆栈中运行 space（因此本质上是迭代的），或者不是（因此本质上是递归的）。

方案有尾调用优化，所以你的代码实际上是

private int iterativeSum(int x, int y)
{
ITERATIVE_SUM:
    System.out.println("x "+x+" y "+y);
    if(x == 0)
    {
        goto RETURN;
    }
    --x;    // return iterativeSum(--x, ++y);
    ++y;
    goto ITERATIVE_SUM;
RETURN:
    return y
}

相当于标准的while循环，因为尾递归函数调用重用函数调用框架。

迭代函数可以调用自身吗？

Could an iterative function call itself?

java

iteration

recursion

scheme

sicp

一个合适的蹦床