Need Help Understanding Recursive Function Example From Eloquent Javascript

function power(base, exponent) { if (exponent == 0) return 1; else return base * power(base, exponent - 1); } I think that I understand the basic principle of recursion, it

Solution 1:

I consider each recursive step (the function calling itself) producing a shorter and easier problem.

The easiest problem is power(base, 0), which satisfies exponent == 0 and returns one (any base to the zeroth power is 1).

Then, notice that no matter how large exponent is, it is reducing exponent by one, guaranteeing that it will eventually reach the "easiest" problem where the exponent is zero. It only can't be negative, or else this "base case" is never reached.

So, 2^5, or power(2, 5), becomes 2 * 2^4. And 2^4 = 2 * 2^3. By continuing this expansion, we get 2 * 2 * 2 * 2 * 2 * 1, which equals 32. The 1 represents the case exponent == 0 being true.

The computation has to keep track how many of these multiplications it has accumulated, and once the base case of exponent == 0 is reached, multiply all numbers together. It cannot know in advance with certainty what power(base, exponent-1) will return.

Solution 2:

Follow the call pattern.. Let's assume we do power(2,2).. You get this:

power(2,2) -> (exponent != 0) 2 * power(2, 1)

2 * power(2, 1) -> (exponent != 0) 2 * power(2, 0)

2 * 2 * power(2,0) -> (exponent == 0) 1

2 * 2 * 1 = 4

The way it works is basically your call stack, as long as you keep calling sub-methods, your parent doesn't return. So it keeps nesting itself until it hits a concrete # -- in this case, 1, then it goes back up the stack actually doing the *.

Solution 3:

This shows intermediate results which may help you to follow the logic: Each level has its own value of base, exponent, answer.

function power(base, exponent) {
  var answer; // local
  level = level + 1;
  console.log("Entering: power(" + base + ", " + exponent + 
      ") (level " + level + ")");
  if (exponent == 0) { // don't recurse any more
    answer = 1; }
  else {               // recurse to get answer
    answer = base * power(base, exponent - 1); }
  // now return answer
  console.log("Leaving: power("+ base + ", " + exponent + 
      ") (level " + level + ") ans=" + answer);
  level = level - 1return answer;
  }
var level = 0; // global
console.log("Final answer: " + power(2, 5)); 

Solution 4:

The best way to explain the above recursive is to see what the console returns

function power(base, exponent) {
     // termination/base caseif (exponent == 0)
        return1;
     // recursive caseelse
        console.log(base + ':' + exponent)
        returnbase * power(base, exponent - 1);

     //  2 * (2, 4) = 4//  4 * (2, 3) = 8//  8 * (2, 2) = 16//  16 *(2, 1) = 32//  16 *(2, 0) = 1 recursive stops and returns 1//  function calls the last return  = 32

  } 

  var result = power(2,10)
  console.log(result)

I hope this give you a more visual view of how this recursive works

Solution 5:

This also confused heck out of me when i first saw it, after 10 minutes starring at it, it just came to me....nothing magical....

function power(base, exponent) {
  if (exponent == 0)
  return1;
elsereturnbase * power(base, exponent - 1);
}

console.log(power(2, 5));

this is how it runs through:

returnbase * power(base, exponent - 1)

looking at the above line itself, I was lost too. there are no operations(+,-,*,/,%) done to the given parameters 2 and 5, but somehow at the end, console.log just know to produce correct number.

Because it does not return a numeric value, it simply returns base * power(base, exponent -1) itself, when program reaches power(base, exponent -1), it executes it before return happens, until exponent == 0 becomes true.

1st: return base * power(base, 5 - 1);

2nd: return base * base * power(base, 4 - 1);

3rd: return base * base * base * power(base, 3 - 1);

4th: return base * base * base * base * power(base, 2 - 1);

5th: return base * base * base * base * base * power(base, 1 - 1);

6th: return base * base * base * base * base * 1;

because if (exponent == 0) return 1

so: 2*2*2*2*2*1 = 32