Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

crazy recursion issue

J. Kevin Robbins
Bartender
Posts: 1759
19
I'm trying to do a recursive function with Java. No particular reason; just playing around. But this isn't working for me and I'm extremely puzzled.

For some bizarre reason, when it hits the return on line 18 it jumps back to line 16 and does this several times. The output I get is:

I've been single-stepping through this and can't see why it's not returning to the main method correctly and I'm really puzzled as to how num gets reset to 1 at one point.

What am I doing wrong?

Sean Corfield
Ranch Hand
Posts: 302
10
Because you're looping over the recursive call (so you have both loops AND recursion going on).

Ulf Dittmer
Rancher
Posts: 42967
73
You're mixing iterative and recursive code. Each invocation of computeFactorial should only compute a single step, not multiple steps. So start by replacing "while" with "if". That won't get you all the way there, but it's a start.

Edit: ... what he said :-)

Tim Cooke
Sheriff
Posts: 2974
123
• 1
First think about how you would calculate the Factorial value manually. Let's start simple and say we want to calculate the factorial of 3. How would you do it?

Here's a hint: factorial(n) = n * factorial(n - 1)

Edit: Considering that you posted this in the Functional Programming forum there is a secondary issue with your code other than the recursion. The fact that your class is using local mutable variables means that you are not implementing functional programming which opens you up to concurrency issues if you had multiple threads running through your code at once.

Try and see if you can implement it without any mutable variables.

J. Kevin Robbins
Bartender
Posts: 1759
19
I wasn't really going for a purely functional solution, just a recursive method. Every time I take a class on functional programming I fail because I just can't seem to get my head wrapped around designing recursive solutions. I thought it might be easier using a language I'm familiar with instead of trying to learn FP and a new language like Scala or Haskell (tried both and failed miserably).

I'll bang my head against the wall on this one some more and see if I can get it working.

Ulf Dittmer
Rancher
Posts: 42967
73
I agree with Tim that using an accumulator variable is a sign of iterative design, not functional design.

chris webster
Bartender
Posts: 2407
32
Well, there are plenty of examples online that show how to do this, but I'm guessing you want to figure it out for yourself?

Here's some points to bear in mind:

• Sketch out how to process one input value and return the required output.
• Figure out what your stopping condition is, and what to return when you get there.
• Include the check for the stopping condition and corresponding return value in your function.
• Make sure that each time you call your recursive function with any other value, your next call will be closer to your stopping condition.

• Also, watch out if you call your purely recursive function with a larger value, as you'll hit problems eventually with all these recursive calls blowing the stack.

HTH!

PS: If you really want to play around with recursion, I can recommend The Little Schemer. It's an odd but very effective little book, which aims to teach you recursive thinking via a series of simple questions and answers. It's based on Scheme (a Lisp dialect), but you can use it easily with Racket (Racket is a variety of Scheme) and strictly speaking you don't even need to run the code, just follow the exercises in the book.