javascript - 无法获得javascript递归

Question

这个问题已经有答案了:

How does this recursion work? (11 个回答)

已关闭 8 年前。

这个例子来自 Eloquant javascript，我不明白它是如何工作的。我从其他基本示例中了解了递归的基本工作原理。谁能向我解释一下这是如何工作的？

下面的链接对此进行了解释。 http://eloquentjavascript.net/03_functions.html

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

findSolution(24));
//answer
//"(((1 * 3) + 5) * 3)"

Answer 1

首先，您需要了解内部函数的返回如何工作。

return func(A) || func(B)

如果 func(A) 不为 null，则返回，否则返回 func(B)

现在我们的目标是 24，起点是 find(1, 1) (触发递归函数的外部函数的返回值)

find(1, 1) 可能有两个可能的输出:

A: find(6, (1+5))
or
B find(3, (1*3))

除非我们从 A 获得空返回(或达到目标)，否则 B 将被搁置，因此我们继续 A，返回将是:

Aa: find(11, ((1+5)+5))
or
Ab: find(15, ((1+5)*3))

再次将 Ab 搁置，我们继续 Aa，它将返回:

Aa1: find(16, (((1+5)+5)+5))
Aa2: find(33, (((1+5)+5)*3))

Aa2 大于目标 (24)，因此它永远不会继续。所以我们继续 Aa1，它将返回 21，然后是 25，它通过了目标，因此返回 null。所以我们回到 Ab，它返回 45 > 目标。所以 A 无论如何都会返回 null，现在我们尝试 B:

Ba: find(8, ((1*3)+5))
Bb: find(9, ((1*3)*3))

继续执行 Ba，然后返回:

Ba1: find(13, (((1*3)+5)+5))
Ba2: find(24, (((1*3)+5)*3))

我们继续 Ba1，它将返回 18，然后是 23，然后是 28，它比目标大，因此为空。因此，返回到 Ba2，即 24 == target，完成计算并返回其历史记录，即:

(((1*3)+5)*3)

jsfiddle DEMO
您可以看到所有终点的日志(当达到 null 时或最终找到匹配时)。

编辑:
该函数的执行方式如下:

//instead of find I use f
findSolution(24) >
f(1, 1) >
    f(6, (1+5)) >
        f(11, ((1+5)+5)) >
            f(16, (((1+5)+5)+5)) >
                f(21, ((((1+5)+5)+5)+5)) >
                    f(26, (((((1+5)+5)+5)+5)+5)) > NULL
                    f(63, (((((1+5)+5)+5)+5)*3)) > NULL
                f(48, ((((1+5)+5)+5)*3)) > NULL
            f(33, (((1+5)+5)*3)) > NULL
        f(18, ((1+5)*3)) >
            f(23, (((1+5)*3)+5)) >
                f(28, ((((1+5)*3)+5)+5)) > NULL
                f(69, ((((1+5)*3)+5)*3)) > NULL
            f(54, (((1+5)*3)+5)) > NULL
    f(3, (1*3)) >
        f(8, ((1*3)+5)) >
            f(13, (((1*3)+5)+5)) > 
                f(18, ((((1*3)+5)+5)+5)) >
                    f(23, (((((1*3)+5)+5)+5)+5)) >
                        f(28, ((((((1*3)+5)+5)+5)+5)+5)) > NULL
                        f(69, ((((((1*3)+5)+5)+5)+5)*3)) > NULL
                    f(54, (((((1*3)+5)+5)+5)*3)) > NULL
                f(39, ((((1*3)+5)+5)*3)) > NULL
            f(24, (((1*3)+5)*3)) > MATCH