Reputation: 1433

Recursion and the Return Keyword

I'm currently working my way through the Java tutorials and am currently on Recursions.

I have the following code which calculates the factorial of any number passed to the factorial method

public class App {
    public static void main(String[] args) {
        //E.g 4! = 4*3*2*1(factorial 4)
        System.out.println(factorial(4));

    }
    private static int factorial(int value){
        //System.out.println(value);
        if (value == 1){
            return 1;
        }
        return factorial(value - 1)*value;
    }
}

I have trouble understanding the part

if (value == 1){
    return 1;
}
return factorial(value - 1)*value;

My understanding is that the return keyword simply terminates the method, and/or returns a value of the same type declared by the method(i.e int,String, etc).

What happens when the following line is run?

return factorial(value - 1)*value;

the function is returning the total of (value - 1) * value, which would give me

(3)*4 = 12
(2)*3 = 6
(1)*2 = 2

with each passing iteration.However, System.out.println(factorial(4)); gives me a total of 24. How is this number derived from the method? There are no variables to store the sum of the values, so where is the program storing them? Also, how do I get 24 from these values?

(3)*4
(2)*3
(1)*2

While I know that 24 is derived from 4*3*2*1, I do not see how that can be calculated from the above.

Any explanation would be greatly appreciated.

Upvotes: 5

Answers (8)

Kerwin You

Reputation: 51

As I thought, return f(); means execute f() and return the result of f().In recursion , return result; is just a program statement runs after recursion function f(). So it's execution order is contrary to modulated recursion function.

Upvotes: 0

phoog

Reputation: 43046

You've misinterpreted

return factorial(value - 1)*value;

The values being multiplied are factorial(value - 1) and value. In other words, you can rewrite it like this:

return (factorial(value - 1)) * value;

So when you pass 4, you get this:

factorial(3) * 4;

which is equivalent to

(factorial(2) * 3) * 4;

which is equivalent to

((factorial(1) * 2) * 3) * 4;

which is equivalent to

1 * 2 * 3 * 4;

The way this works, which you can see easily if you step through the code with a debugger, is as follows:

The first call to the function passes 4. The function evaluates the if, then calls itself, passing 3. (The state of the first function call is preserved on the stack, so when this call returns, we can resume where we left off, now that we have the result of the function call. This "stack" abstraction is not actually necessary to understand recursion.)
The second function call evaluates the if and calls itself, passing 2.
The third function call evaluates the if and calls itself, passing 1.
The fourth function call evaluates the if and returns 1.
The third function call then resumes, multiplying the return value of the function that just returned (1) with the value of its argument (2), returning the result (2).
The second function call then resumes, multiplying the return value of the function that just returned (2) with the value of its argument (3), returning the result (6).
The first function call then resumes, multiplying the return value of the function that just returned (6) with the value of its argument (4), returning the result (24).

Some optimizing compilers will change recursive calls into loops, but it's not generally possible to change a recursive call to a fixed expression, like 1 * 2 * 3 * 4, because at compile time you don't generally know how deep the recursion will be.

All of this will be abundantly clear if you modify your code as follows and then step through it with a debugger:

private static int factorial(int value){
    if (value == 1){
        return 1;
    }
    int recursiveResult = factorial(value - 1);
    return recursiveResult * value;
}

Note that with each recursive call, we have to store the state of a "suspended" method, waiting for the result of the call, on the stack. For this reason, if a method calls itself recursively (or a chain of methods call themselves in mutual recursion), there is a possibility for the stack to become full. This is known as a stack overflow. It is usually caused by incorrect logic in a function causing a recursive loop:

int stackOverflow() { return stackOverflow(); }

It can also be caused by a function that doesn't logically loop, but calls itself too many times because of the data passed to it. For example, recursive functions are useful when working with tree data structures; if the tree is too tall, it can cause a stackoverflow. So will the following, with some arguments, but not with others:

void possibleStackOverflow(int arg) { if (arg == 0) return; possibleStackOverflow(arg - 1); }

If you call possibleStackOverflow(10) you're probably fine, but possibleStackOverflow(-1) will throw an exception.

Also, by VM implementation limitations, calling possibleStackOverflow(Integer.MAX_VALUE) will throw an StackOverflowException

Upvotes: 10

Always Learning

Reputation: 5581

Your recursive method can end in only two ways. Either value is 1 and it returns 1, or it calls itself with a smaller value-1 and returns the product of whatever that result was and the current value.

The method could have been written more expanded like this:

private static int factorial(int value){
    if (value == 1){
        return 1;
    }
    int a = factorial(value - 1);
    return a * value;
}

From a stack point of view it looks like this. I've inserted fictitious variables a, b and c to indicate the value of the recursive calls as they return.

factorial(4)
  |-- a = factorial(4-1=3)
  |    |-- b = factorial(3-1=2)
  |    |    |-- c = factorial(2-1=1)
  |    |    |    +-- return 1          // <-- deepest point in the stack
  |    |    +-- return c * 2 = 2
  |    +-- return b * 3 = 6
  +-- return a * 4 = 24

If you put a larger starting number, the stack would just get deeper, repeatedly calling factorial(value-1) until it finally got to 1 and then the stack unwinds to reveal the answer. If you put much much larger number, you will end up with a stack overflow (the namesake of this site!) because you'd run out of memory to hold all of the variables needed.

Upvotes: 1

Cyborg

Reputation: 193

The word 'return' does, indeed, break from the current method and return a value/result. However, you have an 'expression' in the return 'statement' that needs to be evaluated before 'return' can exit.

For example, return 1 + 1; needs to evaluate the operation '+' before it returns. When you call return func(arguments); java has to call that function before it returns. In this case, it recursively goes through this "call stack" (function calls are put on a 'stack' where the last one in is the first evaluated).

So, to really describe what is going on here:

1) return statement recognizes an expression

2) the expression calls a function on the stack

3) the function on the stack hits another return with another function to evaluate

4) ...

5) the "base case" is reached, where a '1' is found.

6) the function calls are executed down the stack to evaluate the expression

Upvotes: 1

user

Reputation: 745

To understand recursion try to draw a tree of the calls and the parameters:

factorial(4)  = 4 * factorial(4-1)
                                        |
                                3 * factorial(3-1)
                                               |
                                       2 * factorial(2-1)
                                                      |
                                                      1

Try it with the recursive fibonacci formula.

Upvotes: 1