Recursive C Functions 193
{11
return 1;12
}13
long i nt result = 1;14
while ( n > 0)15
{16
result *= n;17
n - -;18
}19
return result ;20
}21
This function uses while and stores the result in a local variable called result.
“All right, you can use recursion but you don’t have to. Why do you say that factorial
is a bad example?” Recursion can be more flexible than iterative loops, such as while and
for. Every loop can be expressed easily with recursion. However, the reverse can be diffi-
cult. Some problems can be solved naturally by recursion; solving these problems without
recursion can sometimes be awkward. Why is this a bad example? The recursive solution
is actually worse than the iterative solution. This brings us to the second problem: The
recursive solution is slower. Why? Recursive functions must push and pop frames on the
call stack. Pushing and popping frames takes time.
We compared the execution times of both functions. The iterative solution (using while)
is 14% to 38% faster than the recursive solution. This performance difference may not seem a
lot; however, in the next example (Fibonacci numbers), we will see a remarkable performance
difference.
13.6 Fibonacci Numbers
Calculating Fibonacci numbers is another popular example used in teaching recursion.
The numbers are defined as follows:
f(n) =
1 if n is 1
2 if n is 2
f(n − 1) + f(n − 2) if n > 2.
(13.2)
Table 13.1 lists the values of f (n) for n ≤ 10.
This formula is similar to (12.1) in Section 12.1. The difference is the starting values of
f(1) and f (2). Below is a straightforward implementation of the definition:
// fib1 . c1
long i nt fib1 ( in t n)2
{3
i f (( n == 1) || ( n == 2) ) // base case4
{5
return 1;6
}7
// recu rsive case8
return fib (n - 1) + fib ( n - 2) ;9
}10
194 Intermediate C Programming
n f(n)
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
TABLE 13.1: The first ten values of Fibonacci numbers.
If we look at the definition again, we see that it is “top-down”:
f(n) = f (n − 1) + f(n − 2) if n > 2 (13.3)
It computes f(n) by using the values of f (n − 1) and f(n − 2). If n is greater than 2, then
the function computes f (n − 1) by using the values of f (n − 2) and f(n − 3). This process
continues until n is either 1 or 2.
The following implementation does not use recursion. Because the definition itself is
recursive, the iterative solution must take a different approach:
// fib2 . c1
long i nt fib2 ( in t n)2
{3
i f (( n == 1) || ( n == 2) )4
{5
return 1;6
}7
long i nt fna = 1; // as fib (0) now8
long i nt fnb = 1; // as fib (1) now9
long i nt fnc ; // to hold the latest value of fib10
n - -; // star t in g at 1 , not zero11
while ( n > 1)12
{13
fnc = fnb + fna ; // the new value14
fna = fnb ;15
fnb = fnc ;16
n - -;17
}18
return fnc ;19
}20
This may seem a little complex, but it simply calculates the Fibonacci numbers “bottom-
up”. It knows f (1) and f (2) first and stores the values in fna and fnb respectively. Then,
the function computes f(3) by using the sum of f(1) and f (2). This value is stored in fnc.
After computing f (3), the value in fnc is stored in fnb and the value in fnb is stored in
fna. At this point fnb stores f(3) and fna stores f (2), and now fnc is free to store the
fourth Fibonacci number. We are ready to compute f (4), and repeat until we get to n. This
is actually easier to imagine than the recursive case, because the Fibonacci sequence is built
Recursive C Functions 195
FIGURE 13.1: Computing Fibonacci numbers bottom-up without using recursion.
up from smallest to n, just as if you were doing the calculation by hand. Please spend some
time to understand it. Fig. 13.1 illustrates the steps.
Why do we even bother to consider the bottom-up function? Isn’t the recursive function
good enough? It certainly looks simple since it is direct translation from the mathematical
definition. The problem is that the recursive function does a lot of unnecessary work, and
is hence rather slow. Fig. 13.2 shows the ratio of the execution time for the first (recursive,
top-down) and the second (non-recursive, bottom-up) functions. It is readily apparent that
the first function is slower (takes longer) than the second. Moreover, the ratio keeps rising.
Please notice that the vertical axis is in the logarithmic scale. The first function takes as
much as 2,000 times longer than the second when n is 20.
The data in Fig. 13.2 were generated by using the following program:
// fib . c1
#in clude < stdio .h >2
#in clude < stdlib .h >3
#in clude < sys / time .h >4
#d ef in e MAXN 205
#d ef in e REPEAT 1000006
long i nt fib ( i n t n) ;7
long i nt fib2 ( in t n) ;8
int main ( i n t argc , char * argv [])9
{10
int nval , rept ;11
st ruc t timeval time1 ;12
st ruc t timeval time2 ;13
f l o a t intv1 , intv2 ;14
for ( nval = 1; nval <= MAXN ; nval ++)15
{16
196 Intermediate C Programming
FIGURE 13.2: Ratio of the execution times of the recursive and the non-recursive versions
for calculating Fibonacci numbers. The recursive function is much slower and the ratio in
execution time keeps rising.
long i nt fval ;17
getti meofday (& time1 , NULL ) ;18
for ( rept = 0; rept < REPEAT ; rept ++)19
{20
fval = fib ( nval ) ;21
}22
getti meofday (& time2 , NULL ) ;23
intv1 = ( time2 . tv_sec - time1 . tv_sec ) +24
1e -6 * ( time2 . tv_usec - time1 . tv_usec );25
printf (" fib (%2 d) = %ld , time = %f n " ,26
nval , fval , intv1 );27
getti meofday (& time1 , NULL ) ;28
for ( rept = 0; rept < REPEAT ; rept ++)29
{30
fval = fib2 ( nval );31
}32
getti meofday (& time2 , NULL ) ;33
intv2 = ( time2 . tv_sec - time1 . tv_sec ) +34
1e -6 * ( time2 . tv_usec - time1 . tv_usec );35
printf (" fib2 (%2 d ) = %ld , time = % fn " ,36
nval , fval , intv2 );37
printf (" ratio = %f n" , intv1 / intv2 );38
}39
return EXIT _SUCCES S ;40
}41
This program uses gettimeofday to measure the execution time of the two functions.
gettimeofday returns the time, expressed in seconds and microseconds, since 1970-01-01
00:00:00 (UTC). The two values are stored in a structure called struct in C programs.
Structures will be discussed in great detail later in this book. This program measures the
Recursive C Functions 197
difference of time before and after calculating Fibonacci numbers. The basic structure of
measuring a function’s execution time is
1. get the current time, call it t1;
2. call the function;
3. get the current time, call it t2.
The execution time of this function is t2 − t1. This method of measuring execution time
has limitations. The time t1 and t2 has finite precision. If this function’s execution time
is too short, t2 − t1 will be too small (possibly zero). To obtain acceptable accuracy, the
execution time needs to be much longer than the precision. For gettimeofday, the precision
is microseconds; thus, the execution time should be much longer than one microsecond. This
is the reason why the program calls the functions calculating Fibonacci numbers multiple
times between calling gettimeofday. The values may be slightly different when the program
is run multiple times because your computer also runs many other programs. This is the
last few lines of the program’s output:
fib (16) = 987 , time = 2.161532
fib2 (16) = 987 , time = 0.004730
ratio = 456.9 83490
fib (17) = 1597 , time = 3.500462
fib2 (17) = 1597 , time = 0.0050 9 3
ratio = 687.3 08472
fib (18) = 2584 , time = 5.678572
fib2 (18) = 2584 , time = 0.0054 7 4
ratio = 1037 .371704
fib (19) = 4181 , time = 9.399386
fib2 (19) = 4181 , time = 0.0056 7 7
ratio = 1655 .696045
fib (20) = 6765 , time = 15.53051 3
fib2 (20) = 6765 , time = 0.0078 6 2
ratio = 1975 .389648
As you can see, the ratios of the execution time grow from 457 to 1975.
(a)
(b)
(c) (d)
f(5) = f(4) + f(3)
f(3) + f(2)
f(2) + f(1)
f(2) + f(1)
1
1 1
1 1
f(5) = f(4) + f(3)
f(3) + f(2) f(2) + f(1)
f(2) + f(1)
1
1 1
f(5) = f(4) + f(3)
f(3) + f(2) f(2) + f(1)
f(5) = f(4) + f(3)
FIGURE 13.3: Computing f(5) requires calling f (4) and f (3). Computing f(4) requires
calling f(3) and f (2).
Why is there such a large difference in the execution time? Fig. 13.3 illustrates the
sequence of computation. For the first function, to compute f (5), it is necessary to compute
f(4) and f (3). To compute f(4), it is necessary to compute f(3) and f (2). Fig. 13.4 redraws
Fig. 13.3. This looks like a “tree”. You need to use some imagination because the tree’s
“root” is at the top and the branches go downwards. Computing each value requires the
sum of two values, until reaching the bottom, called leaves. The leaves are the base cases,
where the recursion meets the terminating conditions, namely f (1) or f(2).
Let’s do a little more mathematics here to figure out some properties of this tree. By
definition,
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.