Kenneth .J Kenneth .J - 3 months ago 8
Java Question

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.

Answer

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:

  1. 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.)

  2. The second function call evaluates the if and calls itself, passing 2.

  3. The third function call evaluates the if and calls itself, passing 1.
  4. The fourth function call evaluates the if and returns 1.
  5. 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).
  6. 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).
  7. 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