Chapter 13
Recursive C Functions
13.1 Select Balls with Restrictions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
13.2 One-Way Streets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
13.3 The Tower of Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
13.4 Integer Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
13.5 Factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
13.6 Fibonacci Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
13.7 Performance Profiling with gprof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
In this chapter we convert the mathematical formulas from the previous chapter into C
programs. Recall that there are four steps to solving math problems that use recursion.
These steps are also used when writing C functions that use recursion.
1. Identify the argument (or arguments) of a problem. These will be, in general, the
argument (or arguments) for the recursive C function.
2. Express the solution based on the arguments.
3. Determine the simple cases when the solutions are “obvious”. The function has one
(or several) conditions detecting whether this (or these) simple case(s) can be solved
directly. This is usually referred to as the base case.
4. Derive the relationships between complex cases and simpler cases. We call this the
recursive case because the function calls itself with a simplified argument (or several
modified arguments).
A recursive function has the following structure:
return _type func ( a r guments )1
{2
i f ( this is the base case ) /* by checking the arguments */3
{4
solve the problem5
}6
e l s e /* Rec u rsive case */7
{8
func ( simp l ified arguments ) /* fu n ction calls itself */9
}10
}11
A recursive function should first check whether the arguments specify a base case. A
base case means that the function can immediately return the answer. For this reason,
the if condition (or conditions) is called the terminating condition (or conditions) of the
recursive function. The terminating conditions indicate that a base case has been reached.
When the condition is true, the problem is trivial and recursive calls are unnecessary. If the
problem is not simple, then the function enters the recursive case and the function calls itself
with simplified versions of the arguments. The following sections implement the recursive
equations in the previous chapter.
183
184 Intermediate C Programming
13.1 Select Balls with Restrictions
// balls .c1
// f (1) = 22
// f (2) = 33
// f( n) = f (n -1) + f (n -2)4
#in clude < stdio .h >5
#in clude < stdlib .h >6
int f( i n t m)7
// use m instead of n to distin guish m in f and n in main8
{9
/* Base cases */10
i f (m <= 0)11
{12
printf (" Invalid Number %d , must be positive . n" , m) ;13
return -1;14
}15
i f (m == 1)16
{17
return 2; // f (1) = 218
}19
i f (m == 2)20
{21
return 3; // f (2) = 322
}23
/* Recu r sive case */24
int a;25
int b;26
a = f (m - 1) ;27
b = f (m - 2) ;28
return ( a + b );29
}30
int main ( i n t argc , char * argv [])31
{32
int c;33
int n;34
i f ( argc < 2)35
{36
printf (" need 1 integer .n ");37
return EXIT _FAILUR E ;38
}39
n = ( in t ) strtol ( argv [1] , NULL , 10) ;40
c = f (n) ;41
printf (" f(% d) = % d . n" , n , c ) ;42
return EXIT _SUCCES S ;43
}44
The following results were produced by executing this program with different arguments:
Recursive C Functions 185
n f(n)
1 2
2 3
3 5
4 8
5 13
6 21
Understanding how recursive functions work requires a full understanding of the call
stack. If you are unsure about how the call stack works, then please review Chapter 2. Let’s
see what happens when n (in main) is 3, just after finishing line 41, and before running line
42. For simplicity, the call stack does not show argc and argv.
Frame Symbol Address Value
main
n 101 3
c 100 garbage
Calling f will change the call stack as follows:
Frame Symbol Address Value
f
b 106 garbage
a 105 garbage
m 104 3
value address 103 100 (c’s address)
return location 102 line 45
main
n 101 3
c 100 garbage
Since m is greater than 2, the program will call f (m − 1) and assign the result in a.
Recursive calls follow the same procedure as any other function call. As the function is
called, the return location, value address, arguments, and local variables are pushed on to
the call stack.
Frame Symbol Address Value
f
b 111 garbage
a 110 garbage
m 109 2
value address 108 105 (a’s address)
return location 107 line 30
f
b 106 garbage
a 105 garbage
m 104 3
v value address 103 100 (c’s address)
return location 102 line 45
main
n 101 3
c 100 garbage
The value of m is 2 now and it is a base case. The function returns 3 without calling
itself again. The value 3 is written to address 105.
186 Intermediate C Programming
Frame Symbol Address Value
f
b 106 garbage
a 105 garbage → 3
m 104 3
value address 103 100 (c’s address)
return location 102 line 45
main
n 101 3
c 100 garbage
Line 30 calls f again and m is 1 this time.
Frame Symbol Address Value
f
b 111 garbage
a 110 garbage
m 109 1
value address 108 106
return location 107 line 31
f
b 106 garbage
a 105 3
m 104 3
value address 103 100 (c’s address)
return location 102 line 45
main
n 101 3
c 100 garbage
The value of m is 1 and it meets one terminating condition. The function returns 2, and
this value is written to address 106.
Frame Symbol Address Value
f
b 106 garbage → 2
a 105 3
m 104 3
value address 103 100 (c’s address)
return location 102 line 45
main
n 101 3
c 100 garbage
The program has returned to a previous invocation of f. The sum of a and b is 5. This
value is written to the address of 100.
Frame Symbol Address Value
main
n 101 3
c 100 garbage → 5
A recursive function follows the same rules as any other function call. When a function
is called, a new frame is pushed. When a function finishes, the top frame is popped. A
common misconception is that the frames of a recursive function are merged into a single
frame. This is wrong. The call stack handles recursive calls in the same way as non-recursive
calls.
Recursive C Functions 187
13.2 One-Way Streets
// oneway . c1
// impl ement the r ecursive relation for calculati ng2
// the number of po ssibili ties in a city where cars can3
// only move nort h bound or ea stbound4
#in clude < stdio .h >5
#in clude < stdlib .h >6
int f( i n t dx , i n t dy )7
/* Do not need to worry about dx < 0 or dy < 0.8
This is already handled in main . */9
{10
int a , b;11
i f (( dx == 0) || ( dy == 0) )12
{ /* Base case */13
return 1;14
}15
/* Recu r sive case */16
a = f ( dx - 1 , dy );17
b = f (dx , dy - 1) ;18
return ( a + b );19
}20
int main ( i n t argc , char * argv [])21
{22
int deltax , deltay ;23
int c;24
i f ( argc < 3)25
{26
printf (" need 2 positive i ntegers . n" );27
return EXIT _FAILUR E ;28
}29
deltax = ( in t ) strtol ( argv [1] , NULL , 10) ;30
deltay = ( in t ) strtol ( argv [2] , NULL , 10) ;31
i f (( deltax < 0) || ( deltay < 0) )32
{33
printf (" need 2 positive i ntegers . n" );34
return EXIT _FAILUR E ;35
}36
c = f ( deltax , deltay ) ;37
printf (" f(%d , %d) = %d . n" , deltax , deltay , c );38
return EXIT _SUCCES S ;39
}40
This program uses local variables to store the values returned from recursive calls:
a = f ( dx - 1 , dy );18
b = f (dx , dy - 1) ;19
return ( a + b );20
Actually, the local variables are unnecessary. Instead, the three lines can be rewritten as
follows:
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset