CODEWITHSUNDEEP
java
IceTea
IceTea

Reputation: 660

Need help deciphering a factorial code in Java

I've seen answers using a for loop which I understood, however I came across this code recently and I have no idea how it works. 

public class learn {

    public static int factorial (int N){
        if (N<=1 ) return 1; // won't this mean that "1" is returned at the end all the time?
        else return (N*factorial (N-1)); /* since there's no variable storing the sum
                                            I don't get how this is working out either, 
                                            won't it just be returned and lost?*/
    }
    public static void main(String[] args) {
        System.out.println(factorial(4));
    }
}

Coming from a python background, so maybe I am misunderstanding something about returns in java... [Edit] seems like return 1 is also written in Python, so it's probably not a language issue, I just don't get how recursive functions end (I get how the process goes - it's a function that calls itself).

Here's an illustration of how I interpret this code (wrongly):

  1. factorial(4) is called
  2. 4 is more than 1, so the else statement will run -- 4*factorial(3)
  3. factorial(3) is called - else statement runs again -- 3*factorial(2)
  4. factorial(2) is called -- 2*factorial(1). At this point, we have 4*3*2*1 but the fact that the code only stops at the if (N<=1) return 1 line means that 1 is returned instead of the sum right? (I'm obviously wrong because the console printed the right number - 24)

Upvotes: 1

Views: 110

Answers (2)

user3437460
user3437460

Reputation: 17454

won't this mean that "1" is returned at the end all the time?

No, it will only return 1 when N is less than 1. (according to your condition if (N<=1 ) return 1;) For all other cases, it continues recursively.

since there's no variable storing the sum I don't get how this is working out either, won't it just be returned and lost?

When a method returns, it exits the current method and return to the point of invocation and continue from there. For simplicity, take this scenario: methodA calls methodB, and methodB calls methodC:

public void methodA(){
    print("entering method A..");   //(1)methodA invoked..
    methodB();                      //(2)call methodB
    print("exiting method A");      //(8)exit from methodB, continue from here
}

public void methodB(){               
    print("entering method B..");   //(3)mthodB invoked..
    methodC();                      //(4)call methodC
    print("exiting method B");      //(7)exit from methodC, continue from here. exit methodB
}

public void methodC(){
    print("entering method C..");   //(5)methodC invoked..
    print("exiting method C");      //(6)exit methodC, continue from whoever called methodC
}

You will get the outpus as follows:

entering method A..
entering method B..
entering method C..
exiting method C
exiting method B
exiting method A

If you can understand the program flow of methodA B and C. Now try to understand a method calling "itself".

//Let say N is 3.. 
public static void main(String[] args){
    factorial(3);                    //(9)
}

public static int factorial (int N)  //(1)N:3, (3)N:2, (5)N:1
{
    if (N<=1 ) 
        return 1;                    //(6)Ret 1, return and continue from whoever called me
    else 
        return (N*factorial (N-1));  //(2), (4), (7)Ret 2*1, (8)Ret 3*2*1
}

  • At (6), it exits the method by returning 1 and continue from the place which called this method. The place where it was called is at (7).

  • At (7), it exits the method by returning N*1 (which is 2*1 = 2) and continue from the place which called this method. The place where it was called is at (8).

  • At (8), it exits the method by returning N*2 (which is 3*2 = 6) and continue from the place which called this method. The place where it was called is at (9) which is the main method.

Upvotes: 3

Bernard
Bernard

Reputation: 342

The if statement only returns 1 if the parameter N equals or is smaller than 1, otherwise the else clause will be executed. In the else clause, since it returns a product of parameter N and the returning value of factorial(N-1), Java needs to wait for factorial(N-1) to return a value in order to do the multiplication and return the value. There is no need to store the value of parameter N into a field since a parameter is also a variable, just its value is passed from the method's caller.

In your code, the factorial is invoked 4 times.

Upvotes: 0

Related Questions