Ruby Recursion doesn't work?

Question

I was trying to make a recursive algorithm with Ruby and I couldn't do it so I kept popping the stack as it were and each time I tried a simpler recursive algorithm to see where my mistake was..

But I arrived at this:

def fact(n)
  if n==0
    1
  else
    fact(n)*fact(n-1)  
  end
end

puts fact(5)

and

ruby/part2.rb:81: stack level too deep (SystemStackError)

Ok what is going on?

Is it not possible to make recursive algorithms in Ruby??

Seriously? Here's a hint: Option a) Over the course of the 20 years of Ruby's existence, hundreds of thousands of Ruby developers have never noticed that Ruby doesn't actually work. Option b) there's a bug in your code. Which one is more likely? — Jörg W Mittag
– Jörg W Mittag, Commented Mar 13, 2012 at 4:21

Doboy · Accepted Answer · 2012-03-12 23:47:10Z

6

your algorithm is incorrect, it should look like this

def fact(n)
  if n==0
    1
  else
   n*fact(n-1)  
  end
end

puts fact(5)

edited Mar 12, 2012 at 23:47

answered Mar 12, 2012 at 23:08

Doboy

11.2k11 gold badges42 silver badges49 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Felipe Over a year ago

I see.. SO that's it? I can use recursion in Ruby as I would in C or Java?

SJuan76 Over a year ago

More generally, each recursive invocation must decrease the size of the problem (by calling fact(n) you were keeping the size of it). And, of course, factorials are calculated as Doboy says.

Felipe Over a year ago

Ok. Your algorithm is better I agree. But then why does the edited algorithm also give out the same error?

Blacksad Over a year ago

Because when it reaches fact(1), it calls fact(-1), and -1 being different from 0, it goes on and on in negative numbers...

Blacksad Over a year ago

and by the way your algorithm is NOT factorial, it's something else. fact(n) = n * fact(n-1)

emre nevayeshirazi · Accepted Answer · 2012-03-12 23:31:48Z

2

fact(n) * fact(n - 1) is infinite recursion. You need to reduce the problem size in each call.

def fact(n)
  if n <= 0
    1
  else
    n * fact(n - 1)  
  end
end

Or simply,

def fact(n)
  n <= 0 ? 1 : n * fact(n - 1)  
end

edited Mar 12, 2012 at 23:31

answered Mar 12, 2012 at 23:11

emre nevayeshirazi

19.3k12 gold badges67 silver badges82 bronze badges

Comments

Andrei · Accepted Answer · 2012-03-12 23:10:25Z

-1

You have to do something like fact(n-1)*fact(n-2) because otherwise, fact(n),n=5 will be called forever.

answered Mar 12, 2012 at 23:10

Andrei

2871 silver badge6 bronze badges

3 Comments

Andrei Over a year ago

Well yeah, when you do fact(n-2) you skip the check n==0, but if you change the code to check for n<0 it will work. But still using it this way you will end up with one, because the values will drop until they reach value 1.

Doboy Over a year ago

fact(n) != fact(n-1)*fact(n-2) by counter example, (3!) != (2!)*(1!)

Andrei Over a year ago

I never said that I offered a solution to his problem. I only offered a solution to the recursion error. Check yourself better!

Collectives™ on Stack Overflow

Ruby Recursion doesn't work?

3 Answers 3

5 Comments

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related