CODEWITHSUNDEEP
javarecursion
user2341013
user2341013

Reputation:

Factorial of a number using recursion

I have the below recursive function to compute factorial of a number. The program works fine except when I remove the if condition. Can someone explain why?

This is the code that works fine --

public static long factUsingRecursion(int number) {
    if (number == 1) {
        return 1;
    } else {
        return number * factUsingRecursion(number - 1);
    }
}

Without the if condition (Code that throws the error), 

public static long factUsingRecursion(int number) {
    return number * factUsingRecursion(number - 1);
}

I get the stack overflow error.

Exception in thread "main" java.lang.StackOverflowError at birst.FactorialUsingRecursion.factUsingRecursion(FactorialUsingRecursion.java:10)

Request experts to please advise me why this is the case?

Upvotes: 0

Views: 959

Answers (7)

user1460348
user1460348

Reputation: 1

For every integer i, you are calling the function with i -1. Integersa are infinite, so you would never stop calling the function. eg: -1000 would call -1001 and this would keep going as long as JVM has some space in it's stack.

Upvotes: 0

Paul
Paul

Reputation: 141917

Imagine what happens when you call:

factUsingRecursion(3);

With the if:

3*factUsingRecursion(2)
3*2*factUsingRecursion(1)
3*2*1

Without the if:

3*factUsingRecursion(2)
3*2*factUsingRecursion(1)
3*2*1*factUsingRecursion(0)
3*2*1*0*factUsingRecursion(-1)
3*2*1*0*-1*factUsingRecursion(-2)
3*2*1*0*-1*-2*factUsingRecursion(-3)
...
And so on... It will not stop until you encounter the StackOverflow error

Upvotes: 2

TheoretiCAL
TheoretiCAL

Reputation: 20581

The program will no longer work when you remove the if condition because you will just be left with return number * factUsingRecursion(number - 1); and the factUsingRecursion(number - 1) here would have the same return calling return number * factUsingRecursion(number - 1);. Your function constantly calls itself, never able to evaluate to anything. By setting the condition, you function is able to evaluate to a definitive value at some point in the recursive chain, and the first call can evaluate.

Upvotes: 1

Dororo
Dororo

Reputation: 3440

Recursion requires a base case. Without it, it will continue calling the function over and over and never stop. The if statement is the base case, which terminates the recursion. That is why if you remove it, you get a StackOverflowError.

Upvotes: 2

Nick
Nick

Reputation: 4212

This line causing number variable to be decreased by 1

return number * factUsingRecursion(number - 1);

and it will handle all values of number except when it is 1

so this line of code is a break condition 

if (number == 1) {
        return 1;

}

and it prevent you to avoid stackoverflow exception

Upvotes: 2

asafreedman
asafreedman

Reputation: 572

It loses one of the things that makes a recursive function recursive in that it has no exit condition.

All recursive solutions must satisfy three rules or properties: A recursive solution must contain a base case. A recursive solution must contain a recursive case. A recursive solution must make progress toward the base case.

From: Data Structures and Algorithms Using Python

Upvotes: 1

rgettman
rgettman

Reputation: 178333

In recursion, there must always be a base case that stops the recursion. Without the if, you have no base case and nothing stops it. Eventually too many method calls are on the stack and a StackOverflowError results.

Upvotes: 7

Related Questions