scheme: factorial infinite recursion

My textbook explains basic recursion with the age old factorial. The problem with that is that the code given might be a tiny bit buggy if the expectations aren’t kept on the straight and narrow.

The given code from the book is:

(define (factorial n)
  (if (= n 1)
      (* n (factorial (- n 1)))))

I left this code as is. Factorials are easy to understand, pick any n-value and multiply each value below it until you get to 1.

Imagine you made a call to (factorial 2). The result will be 2 because of 1 * 2. Then imagine (factorial 1), and the result being 1 because the truthy-branch of the if-statement is used instead of the calculation branch. So far, so good, right?

Now, imagine you had a call to (factorial 0). What happens? You’re going to get a dreaded infinite recursion error, which will look similar to this:

;Aborting!: maximum recursion depth exceeded

What could cause this behavior? Perhaps the author of this method simply really trusted himself to not miscount in his recursion. Perhaps it was an oversight, but whatever the case, look at the condition that controls the procedure. Notice if (= n 1), and that there is only a single value that will make this procedure stop, and that is 1.

To fix this to accept 0, while not affecting the result of the factorial numerically, you can simply exchange the (= n 1) with (< n 1). This will force a 1 whenever n is less than 1, so that covers 0 and all negative values.

Happy factorial!


  1. Ian:

    Haha! When I ran this and evaluated (factorial 0) it just went until it ran out of allocated memory.

    September 29, 2011 at 2:46 pm |

Leave a Reply

You must be logged in to post a comment.