CODEWITHSUNDEEP
rubyalgorithm
Evanto
Evanto

Reputation: 350

Why in this factorial code (no recursion) the step is -1 instead of +1?

Why in this code for calculating factorial the step is -1, not +1? How it calculates n = 0, if in the program we have only n < 0 and n > 0?

def factorial(n)
  if n < 0
    return nil
  end

  result = 1
  while n > 0
    result = result * n

    n -= 1
  end

  return result
end

Upvotes: 3

Views: 145

Answers (4)

pjs
pjs

Reputation: 19855

1 * 2 * 3 == 3 * 2 * 1, so arithmetically it doesn't matter whether you work your way up or down. However, decrementing the argument n allows it to be used directly in calculating result, as opposed to basing the calculation on an additional separate variable which gets incremented until it hits n.

That said, it's still not a very ruby way of doing things. I'd probably go with something like:

def factorial(n)
  n == 0 ? 1 : (1..n).inject(:*)
end

You also asked how your implementation calculates factorial(0) as 1. If n == 0 the while n > 0 loop is never activated, so from your initialization result = 1 you skip down to the return statement.

Upvotes: 2

nhouser9
nhouser9

Reputation: 6780

It calculates n=0 because result is set to 1 by default. When n is 0, the loop will not run (because n is not > 0), so the default value of result (which is 1) will be returned.

It subtracts one each time so that it can count downward over all the numbers, so

5! = 5 * 4 * 3 * 2 * 1

If it added one each time it would be

5! = 5 * 6 * 7 * 8...

and so on. So not only would it be wrong but it would also be an infinite loop.

Upvotes: 4

Malcolm G
Malcolm G

Reputation: 614

The reason the step is -1 and not +1 is because the while loop is going while n > 0. So if you were to do n += 1, you would have an infinite loop on your hands.

If you were to set up a for loop with an iterator, you could start the iterator and go until iterator <= n. In that case, you would want to do iterator += 1. But in this situation, we just need to multiply all the values from 1-n together, which is not sensitive to order. Because of that, it is simpler and less code to start at n and decrement it until it reaches zero. That is the reason for n -= 1.

Upvotes: 1

Bill the Lizard
Bill the Lizard

Reputation: 405955

The step is -1 so that you multiply together all the values of n * (n -1) * (n - 2) * ... * 1. Since the multiplication starts at n and goes down, you want the step to be negative. (Alternatively, you could start at 1 and go up to n. In that case you would want the step to be +1. That's just not how this implementation works.)

The program still works for an input of 0 because the default is set to result = 1 before the while loop. The body of the loop is skipped in that case.

Upvotes: 3

Related Questions