Recursive Functions
You already know that in C a function can be called by another function. But can a function call itself? The answer is yes. A function can call itself from a statement inside the body of the function itself. Such a function is said to be recursive.
Listing 18.4 contains an example of calling a recursive function to add integers from 1 to 100.
TYPE
Listing 18.4. Calling a recursive function.
1: /* 18L04.c: Calling a recursive function */
2: #include <stdio.h>
3:
4: enum con{MIN_NUM = 0,
5: MAX_NUM = 100};
6:
7: int fRecur(int n);
8:
9: main()
10: {
11: int i, sum1, sum2;
12:
13: sum1 = sum2 = 0;
14: for (i=1; i<=MAX_NUM; i++)
15: sum1 += i;
16: printf("The value of sum1 is %d.\n", sum1);
17: sum2 = fRecur(MAX_NUM);
18: printf("The value returned by fRecur() is %d.\n", sum2);
19:
20: return 0;
21: }
22: /* function definition */
23: int fRecur(int n)
24: {
25: if (n == MIN_NUM)
26: return 0;
27: return fRecur(n - 1) + n;
28: }
After the executable 18L04.exe is created and executed, the following output is displayed on the screen:
OUTPUT
C:\app>18L04
The value of sum1 is 5050.
The value returned by fRecur() is 5050.
C:\app>
ANALYSIS
In the program in Listing 18.4, a recursive function, fRecur(), is declared in line 7 and defined in lines 23_28.
You can see from the definition of the fRecur() function that the recursion is stopped in line 26 if the incoming int variable, n, is equal to the value contained by the enum name MIN_NUM. Otherwise, the fRecur() function is called by itself over and over in line 27. Note that each time the fRecur() function is called, the integer argument passed to the function is decreased by one.
Now, let's have a look at the main() function of the program. The for loop, shown in lines 14 and 15, adds integers from 1 to the value represented by another enum name, MAX_NUM. In lines 4 and 5, MIN_NUM and MAX_NUM are respectively assigned 0 and 100 in an enum declaration. The printf() function in line 16 then prints out the sum of the addition made by the for loop.
In line 17, the recursive function, fRecur(), is called and passed with an integer argument starting at the value of MAX_NUM. The value returned by the fRecur() function is then assigned to an int variable, sum2.
Eventually, the value saved by sum2 is printed out in line 18. From the output, you can see that the execution of the recursive function fRecur() actually produces the same result as the for loop inside the main() function.
NOTE
Recursive functions are useful in making clearer and simpler implementations of algorithms. On the other hand, however, recursive functions may run slower than their iterative equivalents due to the overhead of repeated function calls.
Function arguments and local variables of a program are stored temporarily in a block of memory called the stack. Each call to a recursive function makes a new copy of the arguments and local variables. The new copy is then put on the stack. If you see your recursive function behaving strangely, it's probably overwriting other data stored on the stack.
- 14 views
