Return with a recursive function

Question

I'm curious how return works when using a recursive function. For example, in the factorial function below, x will reach 1 before any calculations can actually occur.

int factorial (int x){ 
    if (x==1){
        return 1;     
}else{
    return x * factorial(x - 1);
    }
}

Suppose x = 3. Following the logic, it seems it should loop 3 times and return 1:

3 != 1
so else: 3 * factorial (2).
What's factorial (2)?
Well return to top: 2 != 1
so else: 2 * factorial (1).
What's factorial (1)?
Return to top: 1 == 1,
so: return 1.

But, of course it will actually return 6. So how does it work, exactly?

You should read a basic recursive tutorial. Basically, you have a Call Stack which is built up until you reach the base case (which in this case is `x == 1`), then the Call Stack is resolved "backwards" until it returns the first function call. — Fabrício Matté, Apr 21 '13 at 01:01
possible duplicate of [Understanding recursion](http://stackoverflow.com/questions/717725/understanding-recursion) — Fabrício Matté, Apr 21 '13 at 01:03
Ah thanks. So essentially the arguments for each invocation are stored under the hood until it reaches the base case at which point it can return the values. It would be nice if more tutorials explained recursion in terms of what's happening in memory. Just going by the code, it looks like von Munchausen pulling himself out of the swamp by his pigtail. :) — user2303355, Apr 21 '13 at 03:55
Duplicate of http://stackoverflow.com/questions/16126907/return-with-a-recursive-function — Peter Walser, Dec 09 '13 at 16:54

score 1 · Answer 1 · answered Apr 21 '13 at 01:00

Every time you say "well what's the value from that recursive call?", you're dropping the x * from the previous iteration. Without doing that:

factorial(3)
3 * factorial(2)
3 * (2 * factorial(1))
3 * (2 * 1)
= 6

Recursive calling is not like a goto to the top of the function again with new arguments.¹ We call the function again with new arguments, but only that invocation has the new argument value: the caller still has the old value of its arguments and variables.

¹ Unless we're talking about tail recursion, which we aren't, and that's just an optimization anyways.

score 1 · Answer 2 · answered Apr 21 '13 at 01:01

It's not returning to top, it's invoking the factorial function inside the factorial function.

Indeed, at the end, it returns 1, but it returns it as a result in the line

return x * factorial(x - 1);

of the previous call to factorial, where x was 2. This in turn returns 2 * 1 to the previous call to factorial where x was 3. So this gives 3 * 2, returning the result - 6 - to the first invocation of the function.

score 0 · Answer 3 · answered Apr 21 '13 at 01:03

A recursive function call is no different from an ordinary function call. So there's no connection between the return of one call and the return of another.

In the example, the first return statement is

return 3 * factorial(2)

which multiplies 3 by the return value of calling factorial with an argument of 2.

But the return value of factorial(2) is

return 2 * factorial(1)

which multiplies 2 by the return value of calling factorial with an argument of 1.

But the return value of factorial(1) is 1.

So return 2 * factorial(1) is the same as return 2 * 1, which is 2.

So return 3 * factorial(2) is the same as return 3 * 2, which is 6.

score 0 · Answer 4 · edited Apr 21 '13 at 01:28

0

In the first step, x = 3. Your function then returns 3 * factorial(2), which itself returns 2 * factorial(1) (since x still isn't equal to 1), and finally, factorial(1) returns 1.

So in the end you get 3 * 2 * 1 = 6.

edited Apr 21 '13 at 01:28

timss

9,982
4
34
56

answered Apr 21 '13 at 01:03

halpsb

1,106
2
18
28

score 0 · Answer 5 · edited Dec 09 '13 at 16:51

Stack frame is a record that is used at run time to store information about a function call, including the parameters, local variables, register values, and return address. For each successive function calls we are pushing stack frame into stack and when any active function (function which is at top of the stack) gets return call, it’s stack frame is popped up from the stack and the function below it gets active. Here is the example.

enter image description here

So, finally the function factorial(3) return value 6.

Return with a recursive function

5 Answers5