时间戳

首页 > 解决方案 > 为什么这个递归会按照它的方式执行？

javascript - 为什么这个递归会按照它的方式执行？

问题描述

代码片段来自 Eloquent Javascript：

function findSolution(target) {
    function find(current, history) {
        if (current == target) {
            return history;
        }
        else if (current > target) {
            return null;
        }
        else {
            return find(current + 5, `(${history} + 5)`) || 
                    find(current * 3, `(${history} * 3)`);
        }
    }
    return find(1, "1");
}

console.log(findSolution(13));

我调试了代码，看看我是否能理解它。没用。

我检查了调用堆栈。似乎在“return null;”之后，程序执行了之前的调用，但这次考虑else return as“call1 is null || call2”。

通过调用堆栈返回两次后（此时 current 为 6，history 为“(1 + 5)”），call1 不再返回 null（因为 current 为 6，history 为“(1 + 5)”），所以current 和 history 如何从 call1 中获取值并使用这些值执行 call2 ？

此外，程序如何决定首先执行 call2 ，因为此时 call1 不返回 null ？（我正在想象一个无限递归，但无论出于何种原因，显然不是这样）

我错过了什么？

标签： javascriptrecursion

解决方案

findSequence(13)
    find(1, "1")
        find(1 + 5, "(1 + 5)") // this becomes null, because both of its nested stacks are null, because both of their nested stacks are null
            find(6 + 5, "((1 + 5) + 5)") // this becomes null, because both of its nested stacks are null
                find(11 + 5, "(((1 + 5) + 5) + 5)"
                    current > target: return null
                find(11 * 3, "(((1 + 5) + 5) * 3)"
                    current > target: return null
            find(6 * 3, "((1 + 5) * 3)") // this becomes null, because both of its nested stacks are null
                find(18 + 5, "(((1 + 5) * 3) + 5)")
                    current > target: return null
                find(18 * 3, "(((1 + 5) * 3) * 3)")
                    current > target: return null
        find(1 * 3, "(1 * 3)") 
            find(3 + 5, "((1 * 3) + 5)")
                find(8 + 5, "(((1 * 3) + 5) + 5)")
                    current == target: return "(((1 * 3) + 5) + 5)"

那么，你会说这是准确的吗？

推荐阅读