Chapter 20 Recursion

20.1 Introduction to Recursion

Concept:

A recursive function is one that calls itself.

A function that calls itself is known as a recursive function.
The following function, message, is a simple example of recursion. It displays a message and then calls itself.

void message()
{
    cout << "This is a recursive function.\n";
    message();
}

This function creates an infinite loop of calls because it has no mechanism to stop.

Note:

The function example message will eventually cause the program to crash. Do you remember learning in Chapter 19 that the system stores temporary data on a stack each time a function is called? Eventually, these recursive function calls will use up all available stack memory and cause it to overflow.

A recursive function requires a control mechanism, similar to a loop, to regulate its repetitions.
The function can be modified to accept an integer argument to control the number of calls.

void message(int times)
{
    if (times > 0)
    {
        cout << "This is a recursive function.\n";
        message(times - 1);
    }
}

In this version, an if statement controls the repetition.
- As long as times is greater than zero, the message is displayed, and the function calls itself.
- Each subsequent call passes times - 1 as the argument, bringing it closer to the stopping condition.
For a call like message(5);, the function will execute its primary logic five times.
Every time the function is called, a new instance of its parameter (times) is created in memory. This cycle repeats until the argument passed is 0.
The depth of recursion refers to the number of times a function calls itself. In the message(5) example, the depth is five.
When the times parameter reaches 0, the if condition becomes false, and the function returns. Control then passes back to the previous function call, and this process continues until all instances have returned.
The following program demonstrates this recursive function.

🗊 Program 20-1

 #include <iostream>
 using namespace std;

 void message(int);

 int main()
 {
     message(5);
     return 0;
 }


 void message(int times)
 {
     if (times > 0)
     {
         cout << "This is a recursive function.\n";
         message(times - 1);
     }
 }

💻 Program Output

To better understand the flow, a modified version can display messages upon entry and exit of each function call.

🗊 Program 20-2

 #include <iostream>
 using namespace std;

 void message(int);

 int main()
 {
     message(5);
     return 0;
 }


 void message(int times)
 {
     cout << "message called with " << times << " in times.\n";

     if (times > 0)
     {
         cout << "This is a recursive function.\n";
         message(times - 1);
     }

     cout << "message returning with " << times;
     cout << " in times.\n";
 }

💻 Program Output

20.2 Solving Problems with Recursion

Concept:

A problem can be solved with recursion if it can be broken down into successive smaller problems that are identical to the overall problem.

Recursion is a powerful tool for solving repetitive problems.
Any problem solvable with recursion can also be solved iteratively (with a loop). Iterative solutions are often more efficient due to the overhead of function calls.
However, some problems are conceptually easier to solve using recursion.
The general approach for a recursive function is:
- If the problem can be solved now, the function solves it and returns. This is the base case.
- If not, the function reduces the problem to a smaller, similar version and calls itself to solve the smaller problem. This is the recursive case.

Reducing a Problem with Recursion

By reducing the problem in each step, the recursive calls eventually reach the base case, stopping the recursion.

Example: Using Recursion to Calculate the Factorial of a Number

The factorial of a non-negative number n, denoted n!, is defined as:
- If n = 0, then n! = 1
- If n > 0, then n! = 1 × 2 × 3 × … × n
The recursive definition is:
- Base Case: factorial(0) = 1
- Recursive Case: factorial(n) = n * factorial(n - 1) for n > 0.
Here is the C++ code for a recursive factorial function:

int factorial(int n)
{
    if (n == 0)
        return 1;                        
    else
        return n * factorial(n - 1);  
}

The following program demonstrates the function.

🗊 Program 20-3

 #include <iostream>
 using namespace std;

 int factorial(int);

 int main()
 {
     int number;

     cout << "Enter an integer value and I will display\n";
     cout << "its factorial: ";
     cin >> number;

     cout << "The factorial of " << number << " is ";
     cout << factorial(number) << endl;
     return 0;
 }


 int factorial(int n)
 {
     if (n == 0)
         return 1;                      
     else
         return n * factorial(n - 1); 
 }

💻 Program Output

In the example run, factorial(4) calls factorial(3), which calls factorial(2), and so on, until the base case factorial(0) is reached. The return values are then multiplied back up the chain of calls.
The problem is reduced with each call (as n approaches 0), ensuring the base case is eventually met, which stops the recursion.

Example: Using Recursion to Count Characters

A recursive function can count the occurrences of a character in a string.

 int numChars(char search, string str, int subscript)
 {
     if (subscript >= str.length())
     {
         return 0;
     }
     else if (str[subscript] == search)
     {
         return 1 + numChars(search, str, subscript+1);
     }
     else
     {
         return numChars(search, str, subscript+1);
     }
 }

The function’s logic is as follows:
- Base case: If the end of the string is reached (subscript >= str.length()), return 0.
- Recursive case 1: If the character at the current subscript matches, return 1 plus the count from the rest of the string.
- Recursive case 2: If the character does not match, return the count from the rest of the string.
The following program demonstrates the numChars function.

🗊 Program 20-4

 #include <iostream>
 #include <string>
 using namespace std;

 int numChars(char, string, int);

 int main()
 {
     string str = "abcddddef";

     cout << "The letter d appears "
          << numChars('d', str, 0) << " times.\n";

     return 0;
 }


 int numChars(char search, string str, int subscript)
 {
     if (subscript >= str.length())
     {
         return 0;
     }
     else if (str[subscript] == search)
     {
         return 1 + numChars(search, str, subscript+1);
     }
     else
     {
         return numChars(search, str, subscript+1);
     }
 }

💻 Program Output

Direct and Indirect Recursion

Direct recursion occurs when a function calls itself.
Indirect recursion occurs when function A calls function B, which in turn calls function A.

Checkpoint

20.1 What happens if a recursive function never returns?
20.2 What is a recursive function’s base case?

20.3 What will the following program display?

#include <iostream>
using namespace std;
void showMe(int arg);
int main()
{
    int num = 0;
    showMe(num);
    return 0;
}
void showMe(int arg)
{
    if (arg < 10)
        showMe(++arg);
    else
        cout << arg << endl;
}

20.4 What is the difference between direct and indirect recursion?

20.3 Focus on Problem Solving and Program Design: The Recursive `gcd` Function

Concept:

The gcd function uses recursion to find the greatest common divisor (GCD) of two numbers.

The greatest common divisor (GCD) of two numbers can be found using Euclid’s algorithm, which has a natural recursive definition:
- gcd(x, y) = y, if y divides x evenly.
- gcd(x, y) = gcd(y, x % y), otherwise.
The C++ implementation of this algorithm is shown in the program below.

🗊 Program 20-5

 #include <iostream>
 using namespace std;

 int gcd(int, int);

 int main()
 {
     int num1, num2;

     cout << "Enter two integers: ";
     cin >> num1 >> num2;

     cout << "The greatest common divisor of " << num1;
     cout << " and " << num2 << " is ";
     cout << gcd(num1, num2) << endl;
     return 0;
 }


 int gcd(int x, int y)
 {
     if (x % y == 0)
         return y;               
     else
         return gcd(y, x % y);  
 }

💻 Program Output

20.4 Focus on Problem Solving and Program Design: Solving Recursively Defined Problems

Concept:

Some mathematical problems are designed for a recursive solution.

Some mathematical problems, like calculating Fibonacci numbers, are inherently recursive.
The Fibonacci sequence is: 0, 1, 1, 2, 3, 5, 8, … where each number is the sum of the two preceding ones.
The series is defined as:
- F₀ = 0
- F₁ = 1
- F_N = F_N-1 + F_N-2 for N ≥ 2.
A recursive C++ function to calculate the nth Fibonacci number is:

int fib(int n)
{
    if (n <= 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return fib(n - 1) + fib(n - 2);
}

The following program uses this function to display the first 10 Fibonacci numbers.

🗊 Program 20-6

 #include <iostream>
 using namespace std;

 int fib(int);

 int main()
 {
     cout << "The first 10 Fibonacci numbers are:\n";
     for (int x = 0; x < 10; x++)
         cout << fib(x) << " ";
     cout << endl;
     return 0;
 }


 int fib(int n)
 {
     if (n <= 0)
         return 0;   
     else if (n == 1)
         return 1;   
     else
         return fib(n - 1) + fib(n - 2);  
 }

💻 Program Output

20.5 Focus on Problem Solving and Program Design: Recursive Linked List Operations

Concept:

Recursion can be used to traverse the nodes in a linked list.

Recursion can be applied to operations on linked lists, such as:
- Counting the number of nodes.
- Displaying the node values in reverse order.
A common pattern is to use a public member function as an interface that calls a private recursive member function, passing the private head pointer as an argument.
The class declaration for a modified NumberList class is shown below.

 #ifndef NUMBERLIST_H
 #define NUMBERLIST_H

 class NumberList
 {
 private:
     struct ListNode
     {
         double value;
         struct ListNode *next;
     };

     ListNode *head;    

     int countNodes(ListNode *) const;
     void showReverse(ListNode *) const;

 public:
     NumberList()
         { head = nullptr; }

     ~NumberList();

     void appendNode(double);
     void insertNode(double);
     void deleteNode(double);
     void displayList() const;
     int numNodes() const
         { return countNodes(head); }
     void displayBackwards() const
         { showReverse(head); }
 };
 #endif

Counting the Nodes in the List

The public numNodes function calls the private recursive countNodes function.
The countNodes function’s logic is:
- If the current node pointer is not null, return 1 plus the result of calling countNodes on the next node.
- Otherwise, return 0.

 int NumberList::countNodes(ListNode *nodePtr) const
 {
     if (nodePtr != nullptr)
         return 1 + countNodes(nodePtr->next);
     else
         return 0;
 }

The following program demonstrates this functionality.

🗊 Program 20-7

 #include <iostream>
 #include "NumberList.h"
 using namespace std;

 int main()
 {
     const int MAX = 10; 

     NumberList list;

     for (int x = 0; x < MAX; x++)
         list.insertNode(x);

     cout << "The number of nodes is "
          << list.numNodes() << endl;
     return 0;
 }

💻 Program Output

Displaying List Nodes in Reverse Order

The public displayBackwards function calls the private recursive showReverse function.
The showReverse function’s logic is:
- If the current node pointer is not null:
  - First, make a recursive call with the next node (nodePtr->next).
  - Then, display the value of the current node (nodePtr->value).
- This order ensures that the display statement for the last node executes first.

void NumberList::showReverse(ListNode *nodePtr) const
{
    if (nodePtr != nullptr)
    {
        showReverse(nodePtr->next);
        cout << nodePtr->value << " ";
    }
}

The following program demonstrates displaying the list in reverse.

🗊 Program 20-8

 #include <iostream>
 #include "NumberList.h"
 using namespace std;

 int main()
 {
     const double MAX = 10.0; 

     NumberList list;

     for (double x = 1.5; x < MAX; x += 1.1)
         list.appendNode(x);

     cout << "Here are the values in the list:\n";
     list.displayList();

     cout << "Here are the values in reverse order:\n";
     list.displayBackwards();
     return 0;
 }

💻 Program Output

20.6 Focus on Problem Solving and Program Design: A Recursive Binary Search Function

Concept:

The binary search algorithm can be defined as a recursive function.

The binary search algorithm can be implemented recursively by repeatedly dividing the search space.
The recursive procedure is:
- If array[middle] equals the search value, the value is found.
- If array[middle] is less than the search value, perform a binary search on the upper half of the array.
- If array[middle] is greater than the search value, perform a binary search on the lower half of the array.
A recursive C++ binary search function is shown here:

int binarySearch(int array[], int first, int last, int value)
{
   int middle;    
   if (first > last)
       return -1;
   middle = (first + last) / 2;
   if (array[middle] == value)
       return middle;
   if (array[middle] < value)
       return binarySearch(array, middle+1,last,value);
   else
       return binarySearch(array, first,middle-1,value);
}

The function takes the array, the first and last subscripts of the search range, and the value to find. It returns the subscript if found, or -1 otherwise.
The program below demonstrates the function.

🗊 Program 20-9

 #include <iostream>
 using namespace std;

 int binarySearch(int [], int, int, int);

 const int SIZE = 20; 

 int main()
 {
     int tests[SIZE] = {101, 142, 147, 189, 199, 207, 222,
                    234, 289, 296, 310, 319, 388, 394,
                    417, 429, 447, 521, 536, 600};
     int empID;    
     int results;  

     cout << "Enter the Employee ID you wish to search for: ";
     cin >> empID;

     results = binarySearch(tests, 0, SIZE - 1, empID);

     if (results == -1)
         cout << "That number does not exist in the array.\n";
     else
     {
         cout << "That ID is found at element " << results;
         cout << " in the array\n";
     }
     return 0;
 }


 int binarySearch(int array[], int first, int last, int value)
 {
     int middle; 

     if (first > last)
         return -1;
     middle = (first + last)/2;
     if (array[middle]==value)
         return middle;
     if (array[middle]<value)
         return binarySearch(array, middle+1,last,value);
     else
         return binarySearch(array, first,middle-1,value);
 }

💻 Program Output

20.7 The Towers of Hanoi

Concept:

The repetitive steps involved in solving the Towers of Hanoi game can be easily implemented in a recursive algorithm.

The Towers of Hanoi is a classic mathematical game that illustrates the power of recursion.
The game consists of three pegs and a set of discs of different sizes.
The goal is to move all discs from a starting peg to a destination peg, following these rules:
- Move only one disc at a time.
- A larger disc cannot be placed on top of a smaller disc.
- All discs must be on a peg, except when being moved.
The complexity of the solution grows with the number of discs.
The recursive algorithm to solve the problem is as follows:
- To move n discs from peg A to peg C using B as temporary:
  - If n > 0:
    1. Move n - 1 discs from A to B, using C as temporary.
    2. Move the remaining disc from A to C.
    3. Move n - 1 discs from B to C, using A as temporary.
The base case is when there are no more discs to move (n = 0).
The C++ function below implements this algorithm, printing the required moves.

void moveDiscs(int num, int fromPeg, int toPeg, int tempPeg)
{
   if (num > 0)
   {
       moveDiscs(num - 1, fromPeg, tempPeg, toPeg);
       cout << "Move a disc from peg " << fromPeg
          << " to peg " << toPeg << endl;
       moveDiscs(num - 1, tempPeg, toPeg, fromPeg);
   }
}

The function takes the number of discs and the peg numbers for the source, destination, and temporary pegs.
The program below demonstrates the function for 3 discs.

🗊 Program 20-10

 #include <iostream>
 using namespace std;

 void moveDiscs(int, int, int, int);

 int main()
 {
     const int NUM_DISCS = 3;   
     const int FROM_PEG = 1;    
     const int TO_PEG = 3;      
     const int TEMP_PEG = 2;    

     moveDiscs(NUM_DISCS, FROM_PEG, TO_PEG, TEMP_PEG);
     cout << "All the pegs are moved!\n";
      return 0;
 }


 void moveDiscs(int num, int fromPeg, int toPeg, int tempPeg)
 {
     if (num > 0)
     {
         moveDiscs(num - 1, fromPeg, tempPeg, toPeg);
         cout << "Move a disc from peg " << fromPeg
              << " to peg " << toPeg << endl;
         moveDiscs(num - 1, tempPeg, toPeg, fromPeg);
     }
 }

💻 Program Output

20.8 Focus on Problem Solving and Program Design: The QuickSort Algorithm

Concept:

The QuickSort algorithm uses recursion to efficiently sort a list.

The QuickSort algorithm is an efficient, recursive sorting routine.
It sorts a list by dividing it into two sublists around a selected value called the pivot.
All elements in the first sublist are less than the pivot, and all elements in the second sublist are greater than the pivot.
The algorithm then recursively calls itself to sort each sublist. The recursion stops when a sublist contains only one element.
The algorithm uses two primary functions: quickSort (recursive) and partition.
The quickSort function’s logic is:

quickSort:
If Starting Index < Ending Index
   Partition the List around a Pivot
   quickSort Sublist 1
   quickSort Sublist 2
End If

The C++ code for quickSort is:

void quickSort(int set[], int start, int end)
{
   int pivotPoint;
   if (start < end)
   {
      pivotPoint = partition(set, start, end);
      quickSort(set, start, pivotPoint - 1);
      quickSort(set, pivotPoint + 1, end);
   }
}

The partition function selects a pivot and rearranges the list elements around it.

int partition(int set[], int start, int end)
{
   int pivotValue, pivotIndex, mid;
   mid = (start + end) / 2;
   swap(set[start], set[mid]);
   pivotIndex = start;
   pivotValue = set[start];
   for (int scan = start + 1; scan <= end; scan++)
   {
      if (set[scan] < pivotValue)
      {
          pivotIndex++;
              swap(set[pivotIndex], set[scan]);
      }
   }
   swap(set[start], set[pivotIndex]);
   return pivotIndex;
}

Note:

The partition function does not initially sort the values into their final order. Its job is only to move the values that are less than the pivot to the pivot’s left, and move the values that are greater than the pivot to the pivot’s right. As long as that condition is met, they may appear in any order. The ultimate sorting order of the entire list is achieved cumulatively, though the recursive calls to quickSort.

A helper swap function is used to exchange values.

void swap(int &value1, int &value2)
{
    int temp = value1;
    value1 = value2;
    value2 = temp;
}

The program below demonstrates the QuickSort algorithm.

🗊 Program 20-11

 #include <iostream>
 using namespace std;

 void quickSort(int [], int, int);
 int partition(int [], int, int);
 void swap(int &, int &);

 int main()
 {
     const int SIZE = 10; 
     int count;           
     int array[SIZE] = {7, 3, 9, 2, 0, 1, 8, 4, 6, 5};

     for (count = 0; count < SIZE; count++)
         cout << array[count] << " ";
     cout << endl;

     quickSort(array, 0, SIZE - 1);

     for (count = 0; count < SIZE; count++)
         cout << array[count] << " ";
     cout << endl;
     return 0;
 }


 void quickSort(int set[], int start, int end)
 {
     int pivotPoint;

     if (start < end)
     {
         pivotPoint = partition(set, start, end);
         quickSort(set, start, pivotPoint - 1);
         quickSort(set, pivotPoint + 1, end);
     }
 }


 int partition(int set[], int start, int end)
 {
     int pivotValue, pivotIndex, mid;

     mid = (start + end) / 2;
     swap(set[start], set[mid]);
     pivotIndex = start;
     pivotValue = set[start];
     for (int scan = start + 1; scan <= end; scan++)
     {
         if (set[scan] < pivotValue)
         {
             pivotIndex++;
             swap(set[pivotIndex], set[scan]);
         }
     }
     swap(set[start], set[pivotIndex]);
     return pivotIndex;
 }


 void swap(int &value1, int &value2)
 {
     int temp = value1;

     value1 = value2;
     value2 = temp;
 }

💻 Program Output

20.9 Exhaustive Algorithms

Concept:

An exhaustive algorithm is one that finds a best combination of items by looking at all the possible combinations.

An exhaustive algorithm finds the best solution by examining all possible combinations.
Recursion is a helpful technique for implementing exhaustive searches.
An example is finding all possible ways to make change for a certain amount of money and identifying the combination with the fewest coins.
The following program uses a recursive function to find the best way to make change.

🗊 Program 20-12

 #include <iostream>
 using namespace std;

 const int MAX_COINS_CHANGE = 100; 
 const int MAX_COIN_VALUES = 6;    
 const int NO_SOLUTION = INT_MAX;  

 void makeChange(int, int, int[], int);

 int coinValues[MAX_COIN_VALUES] = {100, 50, 25, 10, 5, 1 };

 int bestCoins[MAX_COINS_CHANGE];

 int numBestCoins = NO_SOLUTION, 
     numSolutions = 0,           
     numCoins;                   

 int main()
 {
     int coinsUsed[MAX_COINS_CHANGE], 
     numCoinsUsed = 0,                
     amount;                          

     cout << "Here are the valid coin values, in cents: ";
     for (int index = 0; index < 5; index++)
         cout << coinValues[index] << " ";
     cout << endl;

     cout << "Enter the amount of cents (as an integer) "
          << "to make change for: ";
     cin >> amount;
     cout << "What is the maximum number of coins to give as change? ";
     cin >> numCoins;

     makeChange(numCoins, amount, coinsUsed, numCoinsUsed);

      cout << "Number of possible combinations: " << numSolutions << endl;
     cout << "Best combination of coins:\n";
     if (numBestCoins == NO_SOLUTION)
         cout << "\tNo solution\n";
     else
     {
         for (int count = 0; count < numBestCoins; count++)
             cout << bestCoins[count] << " ";
     }
     cout << endl;
     return 0;
 }


 void makeChange(int coinsLeft, int amount, int coinsUsed[],
              int numCoinsUsed)
 {
     int coinPos, 
         count;   

     if (coinsLeft == 0)   
         return;
     else if (amount < 0)  
         return;
     else if (amount == 0) 
     {
         if (numCoinsUsed < numBestCoins)
         {
             for (count = 0; count < numCoinsUsed; count++)
                 bestCoins[count] = coinsUsed[count];
             numBestCoins = numCoinsUsed;
         }
         numSolutions++;
         return;
     }

     coinPos = numCoins - coinsLeft;
     coinsUsed[numCoinsUsed] = coinValues[coinPos];
     numCoinsUsed++;
     makeChange(coinsLeft, amount - coinValues[coinPos],
               coinsUsed, numCoinsUsed);

     numCoinsUsed--;
     makeChange(coinsLeft - 1, amount, coinsUsed, numCoinsUsed);
 }

💻 Program Output

20.10 Focus on Software Engineering: Recursion versus Iteration

Concept:

Recursive algorithms can also be coded with iterative control structures. There are advantages and disadvantages to each approach.

Any algorithm implemented with recursion can also be implemented with iteration (e.g., a while loop).
Disadvantages of Recursion:
- Recursive algorithms are generally less efficient than iterative ones due to the overhead of function calls (allocating memory, storing return addresses, etc.).
Advantages of Recursion:
- Some problems are more naturally and easily solved with recursion (e.g., GCD, QuickSort, Towers of Hanoi).
- For these problems, a recursive solution can lead to a simpler and more elegant design.
With modern computers, the performance impact of recursion is less of a concern. The choice between recursion and iteration is often a design decision based on which approach leads to a clearer and more maintainable solution for the specific problem.

Review Questions and Exercises

Short Answer

What is the base case of each of the recursive functions listed in Questions 12, 13, and 14?
What type of recursive function do you think would be more difficult to debug, one that uses direct recursion, or one that uses indirect recursion? Why?
Which repetition approach is less efficient, a loop or a recursive function? Why?
When should you choose a recursive algorithm over an iterative algorithm?
Explain what is likely to happen when a recursive function that has no way of stopping executes.

Fill-in-the-Blank

The _______________ of recursion is the number of times a function calls itself.
A recursive function’s solvable problem is known as its _______________. This causes the recursion to stop.
_______________ recursion is when a function explicitly calls itself.
_______________ recursion is when function A calls function B, which in turns calls function A.

Algorithm Workbench

Write a recursive function to return the number of times a specified number occurs in an array.
Write a recursive function to return the largest value in an array.

Predict the Output

What is the output of the following programs?

#include <iostream>
using namespace std;
int function(int);
int main()
{
    int x = 10;
    cout << function(x) << endl;
    return 0;
}
int function(int num)
{
    if (num <= 0)
        return 0;
    else
        return function(num - 1) + num;
}

#include <iostream>
using namespace std;
void function(int);
int main()
{
    int x = 10;
    function(x);
    return 0;
}
void function(int num)
{
    if (num > 0)
    {
        for (int x = 0; x < num; x++)
            cout << '*';
        cout << endl;
        function(num - 1);
    }
}

#include <iostream>
#include <string>
using namespace std;
void function(string, int, int);
int main()
{
    string mystr = "Hello";
    cout << mystr << endl;
    function(mystr, 0, mystr.size());
    return 0;
}
void function(string str, int pos, int size)
{
    if (pos < size)
    {
        function(str, pos + 1, size);
        cout << str[pos];
    }
}

Programming Challenges

Iterative Factorial

Write an iterative version (using a loop instead of recursion) of the factorial function shown in this chapter. Test it with a driver program.
Recursive Conversion

Convert the following function to one that uses recursion.
```
void sign(int n)
{
    while (n > 0)
        cout << "No Parking\n";
    n--;
}
```
Demonstrate the function with a driver program.
QuickSort Template

Create a template version of the QuickSort algorithm that will work with any data type. Demonstrate the template with a driver function.
Recursive Array Sum

Write a function that accepts an array of integers and a number indicating the number of elements as arguments. The function should recursively calculate the sum of all the numbers in the array. Demonstrate the function in a driver program.
Recursive Multiplication`

Solving the Recursive Multiplication Problem

Write a recursive function that accepts two arguments into the parameters x and y. The function should return the value of x times y. Remember, multiplication can be performed as repeated addition:
```
7 * 4 = 4 + 4 + 4 + 4 + 4 + 4 + 4
```
Recursive Power Function

Write a function that uses recursion to raise a number to a power. The function should accept two arguments: the number to be raised and the exponent. Assume that the exponent is a nonnegative integer. Demonstrate the function in a program.
Sum of Numbers

Write a function that accepts an integer argument and returns the sum of all the integers from 1 up to the number passed as an argument. For example, if 50 is passed as an argument, the function will return the sum of 1, 2, 3, 4, … 50. Use recursion to calculate the sum. Demonstrate the function in a program.
isMember Function

Write a recursive Boolean function named isMember. The function should accept two arguments: an array and a value. The function should return true if the value is found in the array, or false if the value is not found in the array. Demonstrate the function in a driver program.
String Reverser

Write a recursive function that accepts a string object as its argument and prints the string in reverse order. Demonstrate the function in a driver program.
maxNode Function

Add a member function named maxNode to the NumberList class discussed in this chapter. The function should return the largest value stored in the list. Use recursion in the function to traverse the list. Demonstrate the function in a driver program.
Palindrome Detector

A palindrome is any word, phrase, or sentence that reads the same forward and backward. Here are some well-known palindromes:
- Able was I, ere I saw Elba
- A man, a plan, a canal, Panama
- Desserts, I stressed
- Kayak
Write a bool function that uses recursion to determine if a string argument is a palindrome. The function should return true if the argument reads the same forward and backward. Demonstrate the function in a program.
Ackermann’s Function

Ackermann’s Function is a recursive mathematical algorithm that can be used to test how well a computer performs recursion. Write a function A(m, n) that solves Ackermann’s Function. Use the following logic in your function:
```
If m = 0 then return n + 1
If n = 0 then return A(m-1, 1)
Otherwise,    return A(m-1, A(m, n-1))
```
Test your function in a driver program that displays the following values:
```
A(0, 0) A(0, 1) A(1, 1) A(1, 2) A(1, 3) A(2, 2) A(3, 2)
```

20.1 Introduction to Recursion

Concept:

Note:

20.2 Solving Problems with Recursion

Concept:

Example: Using Recursion to Calculate the Factorial of a Number

Example: Using Recursion to Count Characters

Direct and Indirect Recursion

Checkpoint

20.3 Focus on Problem Solving and Program Design: The Recursive gcd Function

Concept:

20.4 Focus on Problem Solving and Program Design: Solving Recursively Defined Problems

Concept:

20.5 Focus on Problem Solving and Program Design: Recursive Linked List Operations

Concept:

Counting the Nodes in the List

Displaying List Nodes in Reverse Order

20.6 Focus on Problem Solving and Program Design: A Recursive Binary Search Function

Concept:

20.7 The Towers of Hanoi

Concept:

20.8 Focus on Problem Solving and Program Design: The QuickSort Algorithm

Concept:

Note:

20.9 Exhaustive Algorithms

Concept:

20.10 Focus on Software Engineering: Recursion versus Iteration

Concept:

Review Questions and Exercises

Short Answer

Fill-in-the-Blank

Algorithm Workbench

Predict the Output

Programming Challenges

20.3 Focus on Problem Solving and Program Design: The Recursive `gcd` Function