CODEWITHSUNDEEP
javamathrecursionstack
user2895567
user2895567

Reputation:

When are the multiplications done in this recursive factorial function?

I am trying to understand the following problem: 

public class Main {
    public static int fact(int n){
        if (n == 0){
            return 1;
        }else{
            return n * fact(n - 1);
        }
    }
    public static void main(String[] args){
      System.out.print(fact(5));
    }
}

When the compiler goes through and does return n * fact(n - 1); does it actually multiply the n or does it only do that after it reaches the base case, and then multiplies all the values stored in stack?

Note I am still new to this recursion way of coding.

Upvotes: 1

Views: 168

Answers (5)

Prateek
Prateek

Reputation: 1926

It is simple recursion. As in case of any recursion it first drills down to the base case(using stacks) and afterwards does the multiplication(during stack unwinding process)

So, what would happen in case of your example i.e. fact(5)

fact(5) --> 5 * fact(4) // Here another recursive call is made to calculate fact(4)
fact(4) --> 4 * fact(3)//Here another recursive call is made to calculate fact(3)
.
.
.
fact(1) --> 1 * fact(0)// fact(0) is 1 as per your code

From this point onwards the stack unwinds and each fact(n) is now represented by its simplified version. In the end fact(5) --> 5 * fact(4) converts to fact(5) --> 5 * 4 * 3 *2 *1

Upvotes: 0

Joshua Taylor
Joshua Taylor

Reputation: 85883

A good way to see in what order the multiplications are performed, replace n * fact(...) with mult(n, fact(...)) where mult is a method that you write that takes two numbers and returns their product. Then you can add some output printing in mult, and see the order in which the calls are made.

public class FactorialExample {
    // The new mult method.
    private static int mult( final int x, final int y ) {
        System.out.println( "Multiplying "+x+" and "+y+"." );
        return x * y;
    }

    public static int fact(int n){
        if (n == 0){
            return 1;
        }else{
            return mult(n, fact(n - 1)); // using the new mult method
        }
    }

    public static void main(String[] args){
      System.out.print(fact(5));
    }
}

This produces the following output:

Multiplying 1 and 1.
Multiplying 2 and 1.
Multiplying 3 and 2.
Multiplying 4 and 6.
Multiplying 5 and 24.
120

Recall that the left addend is the one corresponding to n, and that the first call to fact had the the largest value. So, the recursive call fact(4) must complete first (producing 24) and then 5 is multiplied with 24.

Upvotes: 1

sandymatt
sandymatt

Reputation: 5612

It will multiply n and fact(n - 1) once fact(n - 1) gets evaluated (which isn't until you hit the base case.

The recursive fact() calls get chained together until the last one has something to return.

Upvotes: 0

Iłya Bursov
Iłya Bursov

Reputation: 24156

1. java tries to output unknown value, so java execute fact with N = 5
  2. tries to multiple 5 by value, which is unknown, it executes fact with N=5-1
    3. tries to multiple 4 by value ..... N=3
      4. tries to multiple 3 by value ..... N=2
        5. tries to multiple 2 by value ..... N=1
          6. tries to multiple 1 by value ..... N=0
            7. returns 1 and go back to 6th item
          8. 1*1 = 1 and go back to 5th item
        9. 2*1 = 2 and go back to 4th item
      10. 3*2 = 6 and go back to 3rd item
    11. 4*6 = 24 and go back to 2nd item
  12. 5*24 = 120 and return to 1st item
13. display 120

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 372982

(A note: the compiler isn't the program that evaluates fact; the program itself does that).

When the program encounters the statement

n * fact(n - 1)

It will compute fact(n - 1) in isolation by calling fact and passing n - 1 as a parameter. Once that function finishes running and returns, it will have a value that it can then multiply by n. The net effect of this is that the multiplications aren't performed until after the point where the base case is reached, at which point the values of n stored on the stack will then be all multiplied together. You can see this by putting a breakpoint at the line

return n * fact(n - 1);

and watching as the program unwinds the recursion to compute the overall value.

Hope this helps!

Upvotes: 0

Related Questions