• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 166
  • Last Modified:

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
0
gudii9
Asked:
gudii9
  • 4
  • 2
  • 2
  • +1
3 Solutions
 
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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
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

Featured Post

Get your problem seen by more experts

Be seen. Boost your question’s priority for more expert views and faster solutions

  • 4
  • 2
  • 2
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now