How does this recursion work?

问题:

This is an example from Eloquent Javascript:

By starting from the number 1 and repeatedly either adding 5 or multiplying by 3, an infinite amount of new numbers can be produced. How would you write a function that, given a number, tries to find a sequence of additions and multiplications that produce that number?

I'm having trouble understanding how the recursion is working here, wondering if someone could write out a couple times how find is getting called or some other explanation.

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

console.log(findSequence(24)); // => (((1 * 3) + 5) * 3)

回答1:

The function runs a rather simple brute force search with backtracking: at each invocation level it tries adding 5 to the number, and see if starting from the resultant number gets you to the goal. If it does, the result is returned; otherwise, the number is multiplied by 3, and the search for the goal continues from that new number. As the recursion goes along, the textual representation of the expression producing the number is passed to the next invocation levels.

The search for 14 goes as follows:

(1,  "1")
(5,  "1+5")
(10, "(1+5)+5")
(15, "((1+5)+5)+5") <<= Fail
(30, "((1+5)+5)*3") <<= Fail
(15, "(1+5)*3") <<= Fail
(3,  "1*3")
(8,  "(1*3)+5")
(13, "((1*3)+5)+5")
(18, "(((1*3)+5)+5)+5") <<= Fail
(39, "(((1*3)+5)+5)*3") <<= Fail
(24,  "((1*3)+5)*3") <<= Fail
(9, "(1*3)*3")
(14, "((1*3)*3)+5) <<= Success!

回答2:

You just have to create the tree of invocations to figure this out:

findSequence(24)
    find(1, "1")
       find(1 + 5, "(1 + 5)")
           find(6 + 5, "((1 + 5) + 5)")
               find(11 + 5, "(((1 + 5) + 5) + 5)"
                   find(16 + 5, "((((1 + 5) + 5) + 5) + 5)"
                       find(21 + 5, "(((((1 + 5) + 5) + 5) + 5) + 5)"
                          start > goal: return null
                       find(21 * 3, "(((((1 + 5) + 5) + 5) + 5) + 5)" 
                          start > goal: return null
                   find(16 * 3, "((((1 + 5) + 5) + 5) * 3)"
                       start > goal: return null
               find(11 * 3, "(((1 + 5) + 5) * 3)"
                   start > goal: return null
           find(6 * 3, "((1 + 5) * 3)")
               find(18 + 5, "(((1 + 5) * 3) + 5)")
                   find(23 + 5, "((((1 + 5) * 3) + 5) + 5)")
                       start > goal: return null
                   find(23 * 3, "((((1 + 5) * 3) + 5) * 3)")
                       start > goal: return null
               find(18 * 3, "(((1 + 5) * 3) * 3)")
                   start > goal: return null
       find(1 * 3, "(1 * 3)") 
           find(3 + 5, "((1 * 3) + 5)")
               find(8 + 5, "(((1 * 3) + 5) + 5)")
                   find(13 + 5, "((((1 * 3) + 5) + 5) + 5)")
                       find(18 + 5, "(((((1 * 3) + 5) + 5) + 5) + 5)")
                           find(23 + 5, "((((((1 * 3) + 5) + 5) + 5) + 5) + 5)")
                               start > goal: return null
                           find(23 + 5, "((((((1 * 3) + 5) + 5) + 5) + 5) + 5)")
                               start > goal: return null
                       find(18 * 3, "(((((1 * 3) + 5) + 5) + 5) * 3)")
                           start > goal: return null
                   find(13 * 3, "((((1 * 3) + 5) + 5) * 3)")
                       start > goal: return null
               find(8 * 3, "(((1 * 3) + 5) * 3)")
                   return "(((1 * 3) + 5) * 3)"
           find(3 * 3, "((1 * 3) * 3)")
               find(9 + 5, "(((1 * 3) * 3) + 5)")
                  find(14 + 5, "((((1 * 3) * 3) + 5) + 5)")
                      find(19 + 5, "(((((1 * 3) * 3) + 5) +5) + 5)")
                         return "(((((1 * 3) * 3) + 5) +5) + 5)"
                      find(19 * 3, "((((1 * 3) * 3) + 5) *3)")
                          start > goal: return null
               find(9 * 3, "(((1 * 3) * 3) * 3)")
                    start > goal: return null

回答3:

The best way for you to learn this would be to trace through the code in the JavaScript debugger.

Have you used the debugger before? It's really fun and enlightening and easy too.

Simply add a debugger; statement where you want the code to stop. A good place would be just before you call findSequence():

debugger;
console.log(findSequence(24));

Now load your page in Chrome with the Developer Tools open. Your code will stop on that debugger; line. Find the button that lets you Step Into your code (over on the right above the Watch Expressions panel). Click that button to step into the findSequence() call. Each time you click it, it will step into the next line of code, which includes going into each recursive call.

Whenever the code is stopped, you can hover the mouse over any variable to view it, or look at the variables in the panel on the right. There is also a Call Stack that will show you exactly where you are in the recursive calls.

I'm sure somebody could explain the recursion to you, but you will learn a lot more if you actually experience it by stepping through your code in the debugger.

回答4:

Simply speaking, find(start,goal) will be called recursively as long as the goal value has not been reached. In each call, the current number will be either multuplied by 3 or incremented by 5. The history variable stores the string with the operations performed. The current operation is appended to that string in every iteration.

Explanation:

function findSequence(goal) {

  // This inner function will be called recursively.
  // 'history' is a string with the current operations "stack"
  function find(start, history) {
    if (start == goal)           // if goal is achieved, simply return the result
                                 // ending the recursion
      return history;
    else if (start > goal)       // return null to end the recursion
      return null;
    else
      // One of the 'find' calls can return null - using ||
      // ensures we'll get the right value.
      // Null will be returned if 'start+5' or 'start*3' is
      // greater than our 'goal' (24 in your example).
      // The following line is where a recursion happens.
      return find(start + 5, "(" + history + " + 5)") ||
             find(start * 3, "(" + history + " * 3)");
  }

  // Start with '1'
  return find(1, "1");
}

回答5:

This function starts with 1 and then tries to either add 5 to it or multiply it by 3. If that is equal to the goal, the function terminates and prints out the expression found. If not, it calls itself recursively with the value at that level until a match is found or until the values become too high.

Does that help?

回答6:

someone could write out a couple times how find is getting called.

Here you go:

find(1, "1") -> find(3, "(1 * 3)")
             -> find(8, "((1 * 3) + 5)")
             -> find(24, "(((1 * 3) + 5) * 3)")

回答7:

The body of find has three exit paths, two that correspond to a condition that stops the recursion and one that recurses:

if (start == goal)
  return history; // stop recursion: solution found
else if (start > goal)
  return null;    // stop recursion: solution impossible
else
  // ...

The third path is actually a "branch", in that it recurses twice (once to try the addition, once for the multiplication):

  return find(start + 5, "(" + history + " + 5)") ||
         find(start * 3, "(" + history + " * 3)");

So what's going on here?

First of all, note that each of these two find calls will evaluate to either a non-empty string (the history of operations) or to null. Since a non-empty string is a "truthy" value and null is a "falsy" value, we take advantage of this by joining them with the || operator; this operator evaluates to its first operand if it is truthy, otherwise to the second operand.

This means that the first recursion branch (+5) will be evaluated first. If there is a sequence of operations that starts by adding 5 and reaches the goal then the description of this sequence will be returned. Otherwise, if there is a sequence that starts by multiplying by 3 and reaches the goal the description of that history will be returned.

If there is no way to reach the goal then the return value will be the null produced by the second branch.

回答8:

If you get rid of the pretty printing stuff, the code is a little easier to read:

function findSequence(goal) {
    function find(start) {
        if (start == goal) {
            return true;
        } else if (start > goal) {
            return false;
        } else {
            return find(start + 5) || find(start * 3);
        }
    }

    return find(1);
}

The outer function, findSequence, dynamically creates a new function called find where goal is taken from the scope of the parent function. You could re-write it like this for clarity:

function findSequence(start, goal) {
    if (start == goal) {
        return true;
    } else if (start > goal) {
        return false;
    } else {
        return findSequence(start + 5, goal) || findSequence(start * 3, goal);
    }
}

Now, you can see a little more clearly what happens. The recursive step is in the final return statement, which tries both start + 5 and start * 3 at each step and picks the branch that eventually returns true.

Follow the logic of findSequence(1, 23) by hand and you'll understand how it works.

回答9:

Lets leave the history parameter, we'll get to it later.

The recursion expands to all possible operations. It starts with the value 1 as start.

1. We first check if we reached our destination: goal, if we did- return true, meaning the path we took is correct.

2. Second, we ask- did we go over the bound (goal)? If we did, we should return false since this path can't help us.

3. Otherwise, lets try our two possiblities (We use OR because we need at least one):

   • Call the same function, but set start to start + 5
   • Call the same function, but set start to start * 3

The history variable keeps the steps we take. So if a function call identifies that start == goal it returns it.

回答10:

Think of the infinite combinations of adding 5 and multiplying by 3 like a binary tree. At the top is the easiest number to calculate, 1 (in effect a "no steps necessary" answer). Down one level and to the left is 1+5, and to the right is 1*3. At each level the equation resolves to a new value (with a more complex history). This equation is navigating through that tree until it finds a node that equates to the goal. If a node on a branch of the tree produces a value greater than your goal, then it returns null (thus halting the further recusing down that branch, this is because both operations only increase the value so once you end up greater than there is no point to keep looking), if the value of a node equates to the goal then it is returned as the answer (along with the path it used to get there). When the value is less than then both paths could potentially hold the answer so it calls find on each. Here is where JavaScript's "truthy" Boolean logic comes in. By using the || (OR) operator JavaScript will first look down the +5 side of the tree. if 0 or null are returned then the other call (to look down the *3) will execute. If any return evaluates to a non false value then it will get returned up the stack and the search will end.

回答11:

goal is your objective and it's set to 24

goal == 24

Now we have this internal function find() that checks to see if start is equal to 24; its not. It also checks to see if start is greater then 24 this is also not true,

find(1 "1")
1 == 24 //false
1 > 24 //false

So it hits the else statement where it calls find again, this is where the null value from the else if() comes in. If the return is null then it calls the || part until it eventually finds the correct answer.

return find(6, "(1 + 5)")
       find(11, "((1 + 5) + 5)")
       find(16, "(((1 + 5) + 5) +5)")
       find(21, "((((1+5) + 5) + 5) +5)")
       //next one returns null!
       //tries * by 3 on 21, 16, and 11 all return null 

so it switches to the ||

return find(3, "(1 * 3)")
       find(8, "((1 * 3) +5)")
       //some calls down +5 path but that returns null
       find(24, "(((1 * 3) + 5) * 3)")

Finally! We have a true return and we have logged the path we took in the history var.