时间戳

首页 > 解决方案 > 这个递归代码究竟是如何工作的？

algorithm - 这个递归代码究竟是如何工作的？

问题描述

我是一名计算机科学菜鸟，最近进入大学。我正在准备这次考试，我必须将递归算法转换为迭代形式。

我觉得这很难，因为在我要报告的这个具体例子中，我完全不明白这个算法到底应该做什么。因此，我不知道如何转换它。希望你能帮助我。

伪代码截图

文本格式：

Algo(A, i, j)
    ret = i
    if (i <= j) then
        ret = Algo(A, i, ⌊(i+j)/2⌋)
        k = ret + 1
        while k <= j && A[k] <= A[ret] do
            k = k + 1
        if k % 2 = 1 then
            ret = Algo(A, k, j) + ret - k
        else 
            ret = Algo(A, k/2, k) + ret - k/2
    return ret

我知道这听起来很愚蠢，但是……我发现这是一个无限循环。鉴于“i”是我们数组的第一个索引，而“j”是最后一个索引，所以永远不会出现“if i<=j”条件为假的情况。给定 i=0，j=4，j 将是 4，然后是 2，然后是 1。1/2 是 0，然后，0/2 是 0。所以 i 总是等于 j。也许我只是以错误的方式看待它。

我真的很挣扎。将其转换为迭代并不是很简单，尽管我的教授给了我一个可以遵循的方案，但我一点也不觉得这很容易。

仅供参考，这是他告诉我要遵循的计划：

while (!termination)
    if (new call) then
        ''simulate the beginning of a new call''
    else 
        ''retrieve context from stack''
        if (first call) then
            ... 
            ''execute second call''
        else
            ...
            ''end simulation''

希望你能帮助我。仅仅了解这个程序是如何工作的，尤其是递归，对我来说意义重大。提前致谢。

标签： algorithmrecursionstackiteration

解决方案

抛开发散问题不谈，该算法等价于

return i

这可以通过调用堆栈深度的归纳来证明。如果 if 条件为假，则返回值为i。否则，我们计算ret = i(as Algo(A, i, floor((i+j)/2)))，然后Algo(A, x, j) - x = 0对 some进行递增x，也可以通过归纳。

推荐阅读