Aussie AI
C++ Recursion Bugs
-
Bonus Material for "Generative AI in C++"
-
by David Spuler, Ph.D.
Recursion Bugs
Recursion is not something you should use often because it's almost always a big slug, if you ask me (you didn't). But recursive algorithms are beautifully elegant, and will keep showing up on university curriculum of your local degree program. Here's a number of ways that recursion can go astray.
Infinite recursion
Recursion refers to a function that calls itself from within its own function body. Recursive functions offer highly elegant solutions to a number of different programming problems. However, they are quite tricky and there are many ways to go wrong. A recursive function requires a number of conditions to operate correctly:
- a base case when recursion stops
- recursive calls operate on "reduced" problems
The need for a base case is simply that if a program always calls itself it will never return. For example, consider the following erroneous factorial function:
int fact1(int n)
{
return n * fact1(n - 1); /* Bug: No base case */
}
This function will never return and the program will probably terminate abnormally after some delay, when the program stack is finally used up. Therefore, a simple rule about recursive functions is that they should contain a selection statement — an if statement, a conditional operator, or a switch statement. Otherwise, all flow paths will lead to a recursive call and infinite recursion cannot be prevented.
Unchanged arguments in recursive call
The idea of "reduced" problems for the recursive call usually refers to a change in the arguments to the recursive function. If the arguments do not change at all, this will cause infinite recursion as illustrated by the following function:
int fact2(int n)
{
if (n == 0) /* base case */
return 1;
else
return n * fact2(n); /* Bug: Unchanged argument */
}
Whenever this function is passed a nonzero argument such as 2, the "else" clause will be executed, but this will again try to compute the factorial of 2, leading to infinite recursion.
Recursive base case never reached
A totally unchanged argument is not the only problem related to the idea of "reduced" problems. The argument must change in a way that it will finally reach the base case. For example, consider if we change the argument to fact2 in the previous example to the correct expression n-1, making the function appear to have correct recursion:
int fact2(int n)
{
if (n == 0) // base case
return 1;
else
return n * fact2(n - 1); // Better
}
The function still contains a dangerous reliability problem. It will work well for positive integers, but if a negative integer is accidentally passed, there will again be infinite recursion because the argument does not approach the base case — it is decremented further away from zero. Therefore, the program should explicitly check for a neg ative value of n, as follows:
int fact3(int n)
{
if(n < 0)
ERROR();
else if(n == 0) /* base case */
return 1;
else
return n * fact3(n - 1);
}
Poor choice of recursive base case
Yet another common error made by novice programmers when first experimenting with recursion is to forget that the base case will always be reached. For example, examine the recursive function to print out a binary tree using an "inorder" tree traversal:
void print_tree(Node *root)
{
if (root == NULL)
printf("Empty tree\n");
else {
print_tree(root->left); /* print left subtree */
printf("%d\n", root->data); /* visit node */
print_tree(root->right); /* print right subtree */
}
}
The intention is to print the error message "Empty tree" for a tree with a NULL root pointer, and it does indeed do this. However, it also prints the message for every NULL pointer in a non-empty tree. The base case is reached many times, and each time this messages is printed. The correct solution is to test for the empty tree before calling the recursive function, and making the base case of the recursive function do nothing. This can be achieved by making print_tree call another function that performs most of the work, as follows:
void print_tree_sub(Node *root)
{
if (root != NULL) {
print_tree_sub(root->left);
printf("%d\n", root->data);
print_tree_sub(root->right);
}
}
void print_tree(Node *root)
{
if (root == NULL)
printf("Empty tree\n");
else
print_tree_sub(root);
}
Indirect recursion
Novice programmers will sometimes use recursive methods incorrectly to achieve the required flow of control. In the example below, the aim is to have a menu repeatedly shown and for the user to make a choice whereupon the program will do what the user requested and return to the menu. The following program achieves this but contains a hidden recursion problem:
void menu(void)
{
char choice;
while(1) { /* infinite loop */
printf("--- MAIN MENU ---\n");
printf("1. Insert\n");
printf("2. Delete\n");
printf("3. Quit\n");
printf("-----------------\n");
printf("\nEnter your choice: \n");
scanf("%c", &choice);
switch(choice) {
case '1':
insert_obj();
break;
case '2':
delete_obj();
break;
case '3': /* quit */
exit(0);
default:
printf("Unknown choice... try again\n\n");
}
} /* infinite loop */
}
void delete_obj(void)
{
/* ... delete something */
menu(); /* go back to menu */
}
void insert_obj(void)
{
/* ... insert something */
menu(); /* go back to menu */
}
There are no directly recursive functions in this example, but there is indirect recursion between the menu function and the insert and delete functions. The insert and delete functions will never return because they call the menu function as their last action. Therefore, the stack is never unwound and the program will gradually run out of stack space, thus causing a subsequent failure because of stack overflow. In the example above, the simple removal of the calls to menu will cause the program to run correctly.
The astute reader will also notice that the program contains a minor error involving scanf and the %c format.
A particular instance of indirect recursion is a call to the special "main" function. Any explicit call to "main" indicates an error due to indirect recursion, and such a program will eventually fail because of stack overflow. The C++ language definition prohibits explicit calls to "main" and compilation should fail with a diagnostic.