Page 77 - Programming Microcontrollers in C

62 Chapter 1 Introduction to C

{
if(n==0)
return 1;
else
return n*factorial(n-1);
}
This surprisingly simple function calculates the factorial. When­
ever you write a recursive routine, it is important to have means of
getting out of the routine. In the above case, when the argument reaches
zero, the function returns a result rather than calling itself again. At
that time the routine will work itself back a level at a time until it
reaches the initial factorial call, and the calculation will be done.
Recursion can create some elegant code in that the code is very
simple—often too simple. There is a cost in the use of recursive code,
and that is stack space. Each time a function call is made, the argu­
ment is placed on the stack and a subroutine call is executed. As a
minimum, the return address is two bytes, and the value of the argu­
ment is also two bytes. Thus, at least four bytes of stack space are
needed for each function call. That is no problem when the factorial
of a small number is calculated. (The factorial of 13 is larger than
can be held in a long, so only small numbers can be considered for
a factorial.) However, if a recursive function is written that calls it­
self many times, it is possible to get into stack overflow problems.
Another interesting recursive routine is the function to calculate
a Fibonacci number. A Fibonacci number sequence is described by
the following function:
long fib(int n)
{
if(n==1)
return 1;
else if(n==0)
return 1;
else
return fib(n-1) + fib(n-2);
}
This sneaky function calls itself twice. Some interesting characteris­
tics of this function are left to the exercises that follow.