CODEWITHSUNDEEP
javarecursion
Swift Everyday
Swift Everyday

Reputation: 281

Unable to understand recursive factorial

I am new to recursive and I'm having trouble understanding how this recursive factorial function is calculated.

When I try to run through the code with my mind, this is how I visualize it:

If number = 4,

1st return: 4 x 3

2nd return: 3 x 2

3rd return: 2 x 1

So in my mind it is (4 x 3) * (3 x 2) * (2 x 1) but obviously the right return would be 4 X 3 X 2 X 1 instead. I want to be able to understand how does it get 4 X 3 X 2 X 1.

 public static long factorial(long number) {
        if (number <= 1)
           return 1;
        else
        {
            System.out.println(number + " x " + (number-1) );
           return number * factorial(number - 1);
        }
     }

Any help and explanation would be greatly appreciated.

Upvotes: 2

Views: 222

Answers (3)

pjs
pjs

Reputation: 19854

Part of the problem is that your print statement is a lie. Change it to

System.out.println("factorial(" + number + ") = " + number + " x factorial(" + (number-1) + ")");

to see what's really happening. Then consider how your printed output resembles the mathematical definition that

     | n * (n-1)!     for n > 1
n! = | 
     | 1              for n == 0,1.

I've found that it helps to understand recursive functions as, well, functions. One big benefit of functions is that they encapsulate their calculations, hiding the specific details. This leads to the "recursive leap of faith"—if you had a function that returned factorial(n-1), regardless of how it accomplishes it, it would be easy to use it to calculate factorial(n) based on the mathematical recurrence definition. Trusting that the function will work makes it (almost) trivial to write the function!

Upvotes: 3

Ehren
Ehren

Reputation: 11

I think the key to understanding how factorials work is that the answer from the last iteration is the answer that gets returned.

Each iteration of factorial must wait for the following iterations before it has a value to return.

The actual operation that is performed is 1*2*3*4, not 4*3*2*1. Values are returned from last to first.

Upvotes: 0

Jon Skeet
Jon Skeet

Reputation: 1500215

Your visualization should be:

If number = 4,

1st return: 4 x (2nd return)

2nd return: 3 x (3rd return)

3rd return: 2 x (4th return)

4th return: 1

That then simplifies to 4 x 3 x 2 x 1, as expected.

Basically, you need to differentiate between "return value x" and "return the result of recursing, passing in value x".

Upvotes: 5

Related Questions