Erlang Central

Recursion

Revision as of 08:36, 2 September 2006 by Rvg (Talk | contribs)

Overview

Recursion occurs when a function calls itself directly or indirectly. The classic example of recursive programming involves computing factorials. The factorial of a number is computed as that number times all of the numbers below it up to and including 1. For example, factorial(5) is the same as 5*4*3*2*1, and factorial(3) is 3*2*1.

An interesting property of a factorial is that the factorial of a number is equal to the starting number multiplied by the factorial of the number immediately below it. For example, factorial(5) is the same as 5 * factorial(4). You could almost write the factorial function simply as this:

factorial(N) ->
   N * factorial(N-1).

The problem with this function, however, is that it would run forever because there is no place where it stops. The function would continually call factorial. There is nothing to stop it when it hits zero, so it would continue calling factorial on zero and the negative numbers. Therefore, our function needs a condition to tell it when to stop. Incidentally, when this function hits 0, the answer would become 0 and be 0 forever afterwards. This is incorrect.

Since factorials of numbers less than 1 don't make any sense, we stop at the number 1 and return the factorial of 1 (which is 1). Therefore, the real factorial function will look like this:

factorial(N) ->
  case N of										
	1 => 1;
	N -> N * factorial(N-1)
  end.

As you can see, as long as the initial value is above zero, this function will terminate. The stopping point is called the base case. A base case is the bottom point of a recursive program where the operation is so trivial as to be able to return an answer directly. All recursive programs must have at least one base case and must guarantee that they will hit one eventually; otherwise the program would run forever or until the program ran out of memory or stack space. The function above does not utilise the pattern matching power of Erlang however, so we rewrite it as:

factorial(1) -> 1;					                (2)				
factorial(N) -> N * factorial(N-1).

In (2) we used pattern matching in the function clause to detect the case N == 1. Essentially the function clause gives us a first level if or case for free, so we can easily avoid lines as in (1).