factorial example challenge

factorial



Hi,

I am working on below challenge
http://codingbat.com/prob/p154669

Psedo code:
1. return the n multiplied by same method call with n-1
I wrote my code as below

public int factorial(int n) {
  return n * factorial(n-1);
}

Open in new window




I am failing below tests

Expected      Run            
factorial(1) → 1      Exception:java.lang.StackOverflowError (line number:2)      X      
factorial(2) → 2      Exception:java.lang.StackOverflowError (line number:2)      X      
factorial(3) → 6      Exception:java.lang.StackOverflowError (line number:2)      X      
factorial(4) → 24      Exception:java.lang.StackOverflowError (line number:2)      X      
factorial(5) → 120      Exception:java.lang.StackOverflowError (line number:2)      X      
factorial(6) → 720      Exception:java.lang.StackOverflowError (line number:2)      X      
factorial(7) → 5040      Exception:java.lang.StackOverflowError (line number:2)      X      
factorial(8) → 40320      Exception:java.lang.StackOverflowError (line number:2)      X      
factorial(12) → 479001600      Exception:java.lang.StackOverflowError (line number:2)      X      
other tests
X      

How to improve/modify my design, code and any other alternate approaches. please advise
LVL 7
gudii9Asked:
Who is Participating?
 
CPColinSenior Java ArchitectCommented:
You need to have a "base case" where the function returns some value without calling itself again. Otherwise, the function calls itself forever and overflows your stack.
0
 
gurpsbassiCommented:
You are missing base case for recursion.
0
 
tel2Commented:
Hi gudii9,

Are you aware that CodingBat has hints for thing like this?

If you go to the link you supplied:
    http://codingbat.com/prob/p154669
then click the "Show Hint" button to the right of the "Go" button, it will give you this help:
Hint:
First, detect the "base case", a case so simple that the answer can be returned immediately (here when n==1). Otherwise make a recursive call of factorial(n-1) (towards the base case). Assume the recursive call returns a correct value, and fix that value up to make our result.
Doing that should mean that you don't have to ask so many questions at EE.

And if you still can't work it out, and just want to see the solution, then you can click the "Show Solution" button, and a solution should appear on the right of the page, but make sure you read the comments in the code, to get a better understanding.
0
Ultimate Tool Kit for Technology Solution Provider

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

 
gudii9Author Commented:
public int factorial(int n) {
  if(n==1){
    return 1;
  }
  return n * factorial(n-1);
}

Open in new window


like above?
Above passed all the tests.

You need to have a "base case" where the function returns some value without calling itself again. Otherwise, the function calls itself forever and overflows your stack.

what is base case. why we need it?
why does functions calls itself forever without base case?
please advise
0
 
gudii9Author Commented:
http://introcs.cs.princeton.edu/java/23recursion/

I am reading more at above link as well
0
 
gudii9Author Commented:
any improvements or alternate approaches?
0
 
tel2Commented:
Hi gudii9,

"what is base case. why we need it?
The answer to those questions are in my post above.  Did you read it?

"why does functions calls itself forever without base case?
Because there will be nothing to stop it from looping if your function simply calls itself regardless of the argument passed to it.

Well, if you consider making it shorter to be an improvement, you could do something like this:
    return n == 1 ? 1 : factorial(n-1);
but many people will find that less readable.
Are you familiar with the above short-hand alternative to the "if...else..." syntax?
0
 
CPColinSenior Java ArchitectCommented:
what is base case. why we need it?
I answered that in the same sentence as I introduced the term.
why does functions calls itself forever without base case?
Because that's what happens when a recursive function has no base case, by definition!
0
 
gudii9Author Commented:
   return n == 1 ? 1 : factorial(n-1);
but many people will find that less readable.
Are you familiar with the above short-hand alternative to the "if...else..." syntax?
yes. I am. I like above approach too
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.