6.8.1. Recursion Examples

recursion

Instructors and textbooks frequently use two common examples to introduce recursion. The text presents both examples as rules, functions, and C++ functions. A third bonus example illustrates elegant, recursive solutions for visiting or traversing the nodes in a binary tree.

Recursion Example 1: The Factorial Function

recursion, factorial function

The factorial function frequently appears in combinatorial and permutation problems. It is only defined on integers, but the gamma function (not covered here) extends the factorial function to real numbers.

The Rule

0! = 1 (base case)
n! = 1 * 2 * 3 * . . . * (n - 1) * n

Recursive Factorial Functional Notation

\[ f(n) = \left\{ \begin{array}{ll} 1 & , n = 0 \\ n(n-1) & , n \gt 0 \\ \end{array} \right. \]

The Recursive C++ Factorial Function

#include <iostream>
using namespace std;

int fact(int n)
{
	if (n > 0)
		return n * fact(n - 1);	// recursion
	else
		return 1;		// non-recursion (base case)
}

int main()
{
	cout << fact(10) << endl;

	return 0;
}
A function to calculate n!. The "false" branch of the if-else-statement implements the non-recursive or base case path through the function. The "true" branch implements the recursive path. Notice that n changes in each recursive call (highlighted).

Recursion Example 2: The Fibonacci Sequence

recursion, fibonacci sequence

Few number sequences can match the ubiquity of the Fibonacci numbers, which appear everywhere from architecture to biology (see Fibonacci Sequence at Math Is Fun). Can you see how the function implements the rule for forming the Fibonacci sequence?

The Rule

x0 = 0 (base case)
x1 = 1 (base case)
xn = xn-1 + xn-2

Recursive Fibonacci Functional Notation

\[ x_n = \left\{ \begin{array}{ll} 0 & , n = 0 \\ 1 & , n = 1 \\ x_{n-1} + x_{n-2} & , n \gt 1 \\ \end{array} \right. \]

The Recursive C++ Fibonacci Function

#include <iostream>
using namespace std;

int fib(int n)
{
	if (n == 0)
		return 0;			// base case
	else if (n == 1)
		return 1;			// base case
	else
		return fib(n - 1) + fib(n - 2);	// recursion
}

int main()
{
	cout << fib(10) << endl;

	return 0;
}
A function to find the nth number in the Fibonacci sequence. This implementation of the Fibonacci sequence has two base cases or non-recursive paths through the function. (We could rewrite both the functional notation and the C++ function to collapse the two base cases into one, but, in general, it is possible to have multiple base cases.)

Recursion Example 3: Walking Binary Trees

recursion, binary tree, in-order, pre-order, post-order

We explored binary trees in chapter 4 as one use of pointers. We can use binary trees again to demonstrate recursion.

A picture of a balanced binary tree - each side has the same height. The tree has three levels. The top level has one node named A. The second has two nodes named left to right, B and C. The third or bottom level has four nodes, left to right: D, E, F, and G. 
struct node
{
	Data	d;
	node*	left;
	node*	right;
};


void display(Data d);
(a)(b)
A binary tree example. Each circle in the picture represents a node, an instance of the node structure. Each node has some data, represented by the letters "A" through "G," and two pointers named left and right, represented by the lines underneath each node. The top node, containing data "A," is called the root, and the nodes at the bottom, "D," "E," "F," and "G," are called leaves.
  1. Binary trees are inherently recursive data structures - any node in the tree is the root of a sub-tree. So, the sub-tree whose root is "B" is also a tree and can be used with any tree operation.
  2. We can conveniently place the structure specification and function prototype in a header file. Furthermore, we are deliberately vague about what we mean by Data and how the display operation works.

The structure specification and the function prototype are sufficient to write a set of small, simple, and quite elegant recursive functions that display the data in a binary tree.

In-orderPre-orderPost-order
void visit(node* n)
{
	if (n->left != nullptr)
		visit(n->left);
	display(n->d);
	if (n->right != nullptr)
		visit(n->right);
}
 
void visit(node* n)
{
	display(n->d);
	if (n->left != nullptr)
		visit(n->left);
	if (n->right != nullptr)
		visit(n->right);
}
 
void visit(node* n)
{
	if (n->left != nullptr)
		visit(n->left);
	if (n->right != nullptr)
		visit(n->right);
	display(n->d);
}
(a)(b)(c)
Recursive binary tree traversal functions. Accessing a tree node is called visiting the node. Formally, computer scientists call visiting all the tree nodes in a particular order traversing the tree, and informally, they call it walking the tree. There are three tree traversal orders: in-order, pre-order, and post-order. By writing visit as a recursive function, we can select a traversal order by where we locate the call to display. Notice that the traversal functions have two recursive paths (highlighted). The visit order for each traversal is as follows:
  1. DBEAFCG
  2. ABDECFG
  3. DEBFGCA

 

enum { INORDER, PREORDER, POSTORDER };

	...

void visit(node* n, int order)
{
	if (order == PREORDER)
		display(n->d);

	if (n->left != nullptr)
		visit(n->left, order);

	if (order == INORDER)
		display(n->d);

	if (n->right != nullptr)
		visit(n->right, order);

	if (order == POSTORDER)
		display(n->d);
}
One function, three traversal orders. The example demonstrates implementing all three traversal algorithms in a single function. It also demonstrates another authentic use for an enumeration.