Understanding execution behind recursion - how does recursion figure out when to stop?

Question

I know there are many threads for recursion here. And technically I do understand the principle behind recursion, I'm just more of curious as to where the actual recursion counter is stored or how does the compiler keep track of it

This is probably better understood by code. I have created a simple recursion function in javascript.

function factorial(number){
    if (number > 1) {
    return number * factorial(number - 1);
  } else {
    return number;
  }
}

Now, everybody understands how this works. We call a recursive function on the factorial which repeats recursively until a function end.

My question would be, how come the factorial function stops executing the recursion at the correct time? If we tried to debug the function in our mind, my understanding is, it would look something like this:

Let's say we called factorial(3);

1. Function Invoked -> Load Arguments
2. Calculcate the IF condition -> 3 > 1 -> apply recursive function
3. 3 * recursive(2) * recursive(1) => 3 * 2 * 1 = 6

Now my question is, how is that possible? How come a) if we reduced the recursive counter to 1, we didn't enter the else { statement given it should be evaluated as false, and b) how come the recursive counter knew, to loop the recursive function only number-Nth amount of times?

For better illustration, I added the following line of code document.write("entered with number " + number + "</br>"); so we'll print it out every time we enter the if condition.

function factorial(number){
 if (number > 1) {
   document.write("entered with number " + number + "</br>");
   return number * factorial(number - 1);
  } else {
   return number;
  }
}

document.write(factorial(3) + "<br/>");

As you can see, the if condition if condition evaluated as true and printed out the message for 3 and 2. How come the counter didn't loop lower and how come we never returned to the initial else { return number; } if we called the recursive operation on factorial(2-1)?

It is pretty difficult question to word, so if you have any idea on how to formulate it better, feel free to edit my question!

Answer 1

Here's a verbal description of what the recursion is doing, in too much detail:

1. You call factorial(3) in your document.write().

2. factorial(3) wants to return 3 * factorial(2). Before it can return a value, it has to work out what factorial(2) means.

3. So now we have that factorial(3) waiting for the results of factorial(2). factorial(2) runs, and wants to return 2 * factorial(1). Before it can return a value it has to work out what factorial(1) means.

4. Now we have factorial(3) waiting for the results of factorial(2), which is waiting for the results of factorial(1). factorial(1) runs, and sees that its input is 1, so hits the "else" block, so just returns 1 to its caller, the factorial(2).

5. Now the factorial(2) has what it needs, so can return 2 * 1 to its caller, the factorial(3).

6. Now the factorial(3) has what it needs, so can return 3 * 2 to its caller.

7. The calling document.write receives "6".

The recursion "knows" where to stop because eventually it reaches a point where it just returns the number 1, instead of returning something that depends on another call to factorial(). If the function always tried to call itself, there'd be no way out of the recursion loop; it would just keep going until the stack overflows.

Except for factorial(1), every call to factorial(n) will end up calling factorial(n-1) -- so note that factorial(0) or factorial(-1) or factorial(1.01) will never wind up reaching 1, so the recursion will just keep running until the stack overflows. When writing recursive functions, it's a good idea to watch for and handle input that will never reach an exit point; in this case you'd want to throw an error if the input is anything other than a positive integer.

How come the counter didn't loop lower and how come we never returned to the initial else { return number; } if we called the recursive operation on factorial(2-1)?

It did, but your document.write inside the function was inside the if block so nothing was printed when the function went into the else block instead. Here's a more verbose version of the same function, which may give you a clearer picture of what happened:

function factorial(number) {
  document.write("entered with number " + number + "<br>");
  if (number > 1) {
    document.write("recursing<br>")
    return number * factorial(number - 1);
  } else {
    document.write("Returning 1<br>")
    return number;
  }
}

document.write(factorial(3) + "<br>");

what exactly determines when does recursion stop? When the recursion of the function returns the same result twice (in this case 1?) or is there some different trigger?

Try not to think of this in terms of there being a "counter" of some sort keeping track of when the function should stop recursing, or a "trigger" that actively stops it -- that's a misleading way to look at it. Each instance of the function knows only what input it received, and what it wants to return. Most of the time what it wants to return happens to include a call to the same function, that's where the recursion comes from; when what it wants to return doesn't involve a function call, the recursion comes to an end.

For this particular function, for any input other than 1, it calls a new instance of itself with input n-1 (and waits for the results before it can return to its parent caller), so the recursion continues. For input of 1, it doesn't call itself, so the recursion ends. That 'else' block is your "trigger" (though, again, that's a misleading way to think of it; it's not "triggering" anything, it's just returning a number instead of calling a function to return its results.)

f(3) calls f(2) which calls f(1) which doesn't call anything. If you edited the function to call itself with n+1 instead of n-1, then f(3) would call f(4) which would call f(5) and so on until you run out of memory.