Recursion

Recursion is the act of circular definition, because when something is defined recursively, it is defined in terms of itself.

Recursion considered conceptually:

The idea behind recursion is that a complex problem is going to be broken down into smaller, easier to handle problems. This process will continue until an "easy to solve" version of the problem is reached.

In C++, recursion is implemented via functions. These recursive functions are simply going to keep calling themselves until it reaches a problem it knows how to handle.

A recursive function knows how to solve only the simplest of problems, the so-called base-case

A function called with the base-case, simply returns a result

A function called with a problem more complex than the base-case, divides the problem into two conceptual pieces:

Since piece 2 is like the original problem, the function calls a fresh copy of itself that is going to work on the smaller version of the problem. This is known as the recursion step.

The recursion step will typically include the keyword return because its result will be combined with piece 1 (the portion of the problem it knew how to handle) to form a result that will be passed back to the original caller

The recursion step executes while the original call is still open (i.e. has not finished executing)

In order for the recursion to eventually terminate, the smaller problems must converge towards the base-case

Once the base-case is reached, a result is returned to the previous copy of the function, and a sequence of returns ensues until the original function call is reached

How to add things up recursively

The first example is a function to add up all the numbers from m to n. That is, when given two positive integers, m and n, where m < n, we want to find m + (m+1) + (m+2) + ... + n. For example: if m = 5 and n = 10, then 5 + 6 + 7 + 8 + 9 + 10 = 45.

We could solve this iteratively:

int Sum(int m, int n)
  {
  int sum = 0;
  
  for (int i = m; i <= n; i++)
    sum += i;
    
  return sum;
  }

In this iterative solution, we built up to the final solution by continually adding a number to a running total.

To solve this problem recursively, we have to figure out how to break it down into smaller sub-problems, such that some of the sub-problems can be solved using the same method that is used to solve the overall problem. The solutions to the sub-problems will then be combined to solve the overall problem.

If there is more than one number in the range of m to n, then the solution is found by adding m to the sum of the numbers in the range of m+1 to n.

Otherwise, m is equal to n, and the solution is just m.

int Sum(int m, int n)
  {
  if (m < n)
    return m + Sum(m + 1, n);  
  else
    return m;
  }

How to multiply things recursively -- A recursive look at factorial

The factorial of nonnegative integer n (written n!) is the product:

So, 5! = 5 * 4 * 3 * 2 * 1 = 120

We could solve this iteratively:

int factorial(int m)
  {
  int f = 1;
  
  for (int i = 2; i <= m; i++)
    f *= i;
    
  return f;
  }

A recursive definition of the factorial function can be found by observing the following relationship:

The base-case is when n <= 1, so 1 is returned

Factorial can be written:

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

Factorial Recursion:

A bad use of recursion:

The sequence of Fibonacci numbers is:

1  1  2  3  5  8  13  21  34  53...

where each number after the two 1s is the sum of the previous two numbers. The computation of the n^th Fibonacci number can be defined recursively as:

f(1) = 1
f(2) = 1
for n > 2  f(n) = f(n - 1) + f(n - 2)

Fibonacci can be written:

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

The picture of the recursion tree for the fibanocci function indicates that there are a number of calls with the same argument.

Recursive functions that don't return a value:

Recursive functions are not required to return values via the return statement. They can pass values back via parameters.

The binary search algorithm is recursive.

Base case 1: If the list being searched is empty, the item being searched for is not in the list and searching can stop.

Base case 2: If the list being searched is not empty, then check the item in the middle of the list, and if this item is the one being searched for, searching can stop.

Recursion step: Search either the sublist preceding the middle element or the sublist following the middle element in the same manner.

void binarySearch(int list[], int first, int last, int item,
                  bool &found, int &loc)
   {
   if (first > last)    //base case 1
      found = false;
   else
      {
      loc = (first + last) / 2;
      
      if (item < list[loc])
        binarySearch(list, first, loc - 1, found, loc);
      
      else if (item > list[loc])
        binarySearch(list, loc + 1, last, found, loc);
      
      else           //base case 2
        found = true
      }
   }

Applying recursion to linked lists

Recursion can be used to print and reverse the order of the items in a linked list.

Printing a list

A linked list can be iteratively printed by:

void LinkedList::print()
  {
  Node *q;
  
  q = headPtr;        /* q points at first node of the list to print */
  
  while (q != NULL)   /* while there are nodes in the list */
    {
    cout << q->data << "  ";      /* print the data at q */
    q = q->link;                  /* move to the next node in the list */
    }
  }

A close look at the iterative solution should show you that there is a basic pattern to printing the list:

1. print data
2. move to next node

This pattern stops when the node is NULL. So the problem could be coded recursively by:

void LinkedList::print(Node *q)
  {
  if (q != NULL)
    {
    cout << q->data << "  ";      /* print the data at q */
    print (q->link);              /* move to the next node in the list */
    }
  }

We do have a slight problem here though. What is it?

To solve the problem, the print function above will be used as a private helper function and a new public version will be written.

void LinkedList::print()
  {
  print (headPtr);
  }

All this public version does is call the private version, passing it the address of the first node in the list.

How can a list be printed in reverse order?

Reversing a list

The problem can be solved iteratively by:

void LinkedList::reverse()
  {
  Node *p, *q, *rev;
  
  q = headPtr;        /* q points at first node of the list to reverse */
  rev = NULL;         /* new reversed list is empty */
  
  while (q != NULL)
    {
    p = q;            /* p points to lists first node */
    q = q->link;      /* q now points at remainder of the list to reverse */
    p->link = rev;    /* link p to the rest of rev */
    rev = p;          /* rev now points to its new first node */
    }
    
  headPtr = rev;      /* reset to new first node in the list */
  }

Let's rethink this solution so that it uses recursion. Again, we are going to need a public and private version of the function:

void LinkedList::reverse()              Node * LinkedList::reverse(Node *p, Node *q)
  {                                       {
  headPtr = reverse(headPtr, NULL);       if (p == NULL)
  }                                         return q;
                                          else
                                            {
                                            Node *save = p->link;  
                                            p->link = q;
                                            return reverse(save, p);
                                            }
                                          }