Recursion

I l @ ve RuBoard

Recursion

C permits a function to call itself. This process is termed recursion . Recursion is a sometimes tricky, sometimes convenient tool. It's tricky to get recursion to end because a function that calls itself tends to do so indefinitely unless the programming includes a conditional test to terminate recursion.

Recursion Revealed

To see what's involved, let's look at an example. The function main() in Listing 9.6 calls the up_and_down() function. We'll term this the "first level of recursion." Then up_and_down() calls itself; we'll call that the "second level of recursion." The second level calls the third level, and so on. This example is set up to go four levels.

Listing 9.6 The recur.c program.

 /* recur.c -- recursion illustration */ #include <stdio.h> void up_and_down(int); int main(void) {   up_and_down(1);   return 0; } void up_and_down(int n) {   printf("Level %d\n", n);    /* print #1 */   if (n < 4)        up_and_down(n+1);   printf("LEVEL %d\n", n);    /* print #2 */ } 

The output looks like this:

 Level 1 Level 2 Level 3 Level 4 LEVEL 4 LEVEL 3 LEVEL 2 LEVEL 1 

Let's trace through the program to see how recursion works. First, main() calls up_and_down() with an argument of 1 . As a result, the formal argument n in up_and_down() has the value 1 , so print statement #1 prints Level 1 . Then, because n is less than 4 , up_and_down() (Level 1) calls up_and_down() (Level 2) with an argument of n + 1 , or 2 . This causes n in the Level 2 call to be assigned the value 2 , so print statement #1 prints Level 2 . Similarly, the next two calls lead to printing Level 3 and Level 4 .

When Level 4 is reached, n is 4 , so the if test fails. The up_and_down() function is not called again. Instead, the Level 4 call proceeds to print statement #2, which prints LEVEL 4 , because n is 4 . Then it reaches the return statement. At this point, the Level 4 call ends, and control passes back to the function that called it, the Level 3 call. The last statement executed in the Level 3 call was the call to Level 4 in the if statement. Therefore, Level 3 resumes with the following statement, which is print statement #2. This causes LEVEL 3 to be printed. Then Level 3 ends, passing control to Level 2, which prints LEVEL 2 , and so on.

If you find this a bit confusing, think about when you have a chain of function calls, with fun1() calling fun2() , fun2() calling fun3() , and fun3() calling fun(4) . When fun(4) finishes, it passes control back to fun3() . When fun3() finishes, it passes control back to fun(2) . And when fun2() finishes, it passes control back to fun1() . The recursive case works the same, except that fun1() , fun2() , fun3() , and fun4() are all the same function.

Recursion Fundamentals

Recursion can be confusing at first, so let's look at a few basic points that will help you understand the process.

First, each level of function call has its own variables . That is, the n of Level 1 is a different variable from the n of Level 2, so the program created four separate variables, each called n , but each having a distinct value. When the program finally returned to the first level call of up_and_down() , the original n still had the value 1 it started with (see Figure 9.4).

Figure 9.4. Recursion variables.

Second, each function call is balanced with a return. When program flow reaches the return at the end of the last recursion level, control passes to the previous recursion level. The program does not jump all the way back to the original call in main() . Instead, the program must move back through each recursion level, returning from one level of up_and_down() to the level of up_and_down() that called it.

Third, statements in a recursive function that come before the recursive call are executed in the same order that the functions are called. For instance, in Listing 9.6 print statement #1 comes before the recursive call. It was executed four times in the order of the recursive calls: Level 1, Level 2, Level 3, and Level 4.

Fourth, statements in a recursive function that come after the recursive call are executed in the opposite order from which the functions are called. For example, print statement #2 comes after the recursive call, and it was executed in this order: Level 4, Level 3, Level 2, Level 1. This feature of recursion is useful for programming problems involving reversals of order. You'll see an example soon.

Finally, although each level of recursion has its own set of variables, the code itself is not duplicated . The code is a sequence of instructions, and a function call is a command to go to the beginning of that set of instructions. A recursive call, then, returns the program to the beginning of that instruction set. Aside from recursive calls creating new variables on each call, they are much like a loop. Indeed, sometimes recursion can be used instead of loops , and vice versa.

Tail Recursion

In the simplest form of recursion, the recursive call is at the end of the function, just before the return statement. It is called tail recursion , or end recursion , because the recursive call comes at the end. Tail recursion is the simplest form because it acts like a loop.

Let's look at both a loop version and a tail recursion version of a function to calculate factorials. The factorial of an integer is the product of the integers from 1 through that number. For example, 3 factorial (written 3! ) is 1*2*3 . The 0! is taken to be 1, and factorials are not defined for negative numbers . Listing 9.7 presents a function that uses a for loop to calculate factorials.

Listing 9.7 The factor.c program.

 /* factor.c -- uses loops to calculate factorials */ #include <stdio.h> long fact(int n); int main(void) {   int num;   printf("This program calculates factorials.\n");   printf("Enter a value in the range 0-16 (q to quit):\n");   while (scanf("%d", &num) == 1)   {      if (num < 0)         printf("No negative numbers, please.\n");      else if (num > 15)         printf("Keep input under 16.\n");      else         printf("%d factorial = %ld\n", num, fact(num));      printf("Enter a value in the range 0-16 (q to quit):\n");   }   return 0; } long fact(int n)          /* loop finds factorial */ {   long ans;   for (ans = 1; n > 1; n--)      ans *= n;   return ans; } 

The test driver program limits input to the integers 0 “15. It turns out that 15! is slightly over 2 billion, which makes 16! much larger than long on our system. To go beyond 15! , you would have to use a type double function.

The loop initializes ans to 1 and then multiplies it by the integers from n down to 2 . Technically, you should multiply by 1 , but that doesn't change the value. Here's a sample run:

 This program calculates factorials. Enter a value in the range 0-16 (q to quit):  4  4 factorial = 24 Enter a value in the range 0-16 (q to quit):  11  11 factorial = 39916800 Enter a value in the range 0-16 (q to quit):  q  

Now let's try a recursive version. The key is that n! = n ‘ (n-1)! . This follows because (n-1)! is the product of all the positive integers through n-1 . Therefore, multiplying by n gives the product through n . This suggests a recursive approach. If you call the function rfact() , then rfact(n) is n * rfact(n-1) . You can thus evaluate rfact(n) by having it call rfact(n-1) , as in Listing 9.8. Of course, you have to end the recursion at some point, and you can do this by setting the return value to 1 when n is .

Listing 9.8 rfactor.c .

 /* rfactor.c -- uses recursion to calculate factorials */ #include <stdio.h> long rfact(int n); int main(void) {   int num; printf("This program calculates factorials.\n");   printf("Enter a value in the range 0-16 (q to quit):\n");   while (scanf("%d", &num) == 1)   {      if (num < 0)         printf("No negative numbers, please.\n");      else if (num > 15)         printf("Keep input under 16.\n");      else         printf("%d factorial = %ld\n", num, rfact(num));      printf("Enter a value in the range 0-16 (q to quit):\n");   }   return 0; } long rfact(int n)    /* recursive function */ {   long ans;   if (n > 0)      ans= n * rfact(n-1);   else      ans = 1;   return ans; } 

The recursive version of Listing 9.8 produces the same output as the previous version. Note that although the recursive call to rfact() is not the last line in the function, it is the last statement executed when n > 0 , so it is tail recursion.

Given that you can use either a loop or recursion to code a function, which should you use? Normally, the loop is the better choice. First, because each recursive call gets its own set of variables, recursion uses more memory; each recursive call places a new set of variables on the stack. Second, recursion is slower because each function call takes time. So why show this example? Because tail recursion is the simplest form of recursion to understand, and recursion is worth understanding because in some cases, there is no simple loop alternative.

Recursion and Reversal

Now let's look at a problem in which recursion's ability to reverse order is handy. (This is a case for which recursion is simpler than using a loop.) The problem is this: Write a function that prints the binary equivalent of an integer. Binary notation represents numbers in terms of powers of 2. Just as 234 in decimal means 2 x 10 ² + 3 x 10 ¹ + 4 x 10 , so 101 in binary means 1 x 2 ² + 0 x 2 ¹ + 1 x 2 . Binary numbers use only the digits 0 and 1.

You need a method, or algorithm . How can you, say, find the binary equivalent of 5? Well, odd numbers must have a binary representation ending in 1. Even numbers end in 0, so you can determine whether the last digit is a 1 or a 0 by evaluating 5 % 2 . If the result is 1, then 5 is odd, and the last digit is 1. In general, if n is a number, the final digit is n % 2 , so the first digit you find is the last digit you want to print. This suggests using a recursive function in which n % 2 is calculated before the recursive call but in which it is printed after the recursive call. That way, the first value calculated is the last value printed.

To get the next digit, divide the original number by 2. This is the binary equivalent to moving the decimal point one place to the left so that you can examine the next binary digit. If this value is even, the next binary digit is 0. If it is odd, the binary digit is 1. For example, 5/2 is 2 (integer division), so the next digit is 0. This gives 01 so far. Now repeat the process. Divide 2 by 2 to get 1. Evaluate 1 % 2 to get 1, so the next digit is 1. This gives 101. When do you stop? You stop when the result of dividing by 2 is less than 2 because as long as it is 2 or greater, there is one more binary digit. Each division by 2 lops off one more binary digit until you reach the end. (If this seems confusing to you, try working through the decimal analogy. The remainder of 628 divided by 10 is 8, so 8 is the last digit. Integer division by 10 yields 62, and the remainder from dividing 62 by 10 is 2, so that's the next digit, and so on.) Listing 9.9 implements this approach.

Listing 9.9 The binary.c program.

 /* binary.c -- prints integer in binary form */ #include <stdio.h> void to_binary(int n); int main(void) {   int number;   printf("Enter an integer (q to quit):\n");   while (scanf("%d", &number) == 1)   {      printf("Binary equivalent: ");      to_binary(number);      putchar(`\n');      printf("Enter an integer (q to quit):\n");   }   return 0; } void to_binary(int n)   /* recursive function */ {   int r;   r = n % 2;   if (n >= 2)      to_binary(n / 2);   putchar(`0' + r);   return; } 

In Listing 9.9, the expression `0' + r evaluates to the character `0' if r is and to the character `1' if r is 1 . This assumes that the numeric code for the `1' character is one greater than the code for the `0' character. Both the ASCII and the EBCDIC codes satisfy that assumption.

Here's a sample run:

 Enter an integer (q to quit):  9  Binary equivalent: 1001 Enter an integer (q to quit):  255  Binary equivalent: 11111111 Enter an integer (q to quit):  1024  Binary equivalent: 10000000000 Enter an integer (q to quit):  q  

Could you use this algorithm for calculating a binary representation without using recursion? Yes, you could. But because the algorithm calculates the final digit first, you'd have to store all the digits somewhere (in an array, for example) before displaying the result. Chapter 15, "Bit Fiddling," shows an example of a non-recursive approach.

Recursion is used in many more advanced algorithms, often involving cases where the recursive function calls itself twice. For example, there are sorting algorithms that divide the items to be sorted into two groups, then recursively divide each of those groups into two groups, and so on.

I l @ ve RuBoard