C++ Tutorial: Quiz - Recursion

List of C++ Tutorials

List of codes using recursion

Printing a String Reversed
Factorial
Greatest Common Divisors
Fibonacci Sequence
Binary Search
String Permutations
String Combinations
Subsets of a Set

Codes - Recursion

Recursion is a deceptively simple concept. Any routine that calls itself is recursive. The concept is quite simple and clear, however, understanding and applying recursion can be amazingly complex.

Recursion is useful for tasks that can be defined in terms of similar subtasks. For instance, sort, search, and traversal problems often have simple recursive solutions. A recursive routine performs a task in part by calling itself to perform the subtasks. However, a recursive program cannot call itself always, or it would never stop. So, at some point, the routine encounters a subtask that it can perform without calling itself. This case is called the base case. The other case, in which the routine calls itself to perform a subtask, is called as recursive case.

Your Ad Here

Many interesting algorithms are simply expressed with recursive programs, and many algorithm designers prefer to express methods recursively.

There are usually fewer local variables in a recursive routine than in an iterative routine. Also, the iterative version always contains a loop, whereas the recursive version always contains a selection statement—either an If or a Switch. A branching structure is the main control structure in a recursive routine; a looping structure is the main control structure in an itera- tive routine.

Any problem that can be solved recursively can also be solved iteratively. We often find nonrecursive alternatives that achieve the same final result through a different sequence of computations while the recursive formulation provides a structure within which we can seek more efficient alternatives. Iterative algorithms are often quite easy to write, even for tasks that might appear to be fundamentally recursive. Iterative solutions are usually more efficient than recursive solutions.

Printing a String Reversed

Here we have two print functions, one for normal and the other one for printing a string in reverse.

#include <iostream>

using namespace std;

void normalPrint(char *s)
{
	if(*s) {
		putchar(*s);
		normalPrint(s+1);
	}
}
void reversePrint(char *s)
{
	if(*s) {
		reversePrint(s+1);
		putchar(*s);
	}
}

int main() 
{
	char *str = "Normal or Reverse";
	normalPrint(str);
	cout << endl;
	reversePrint(str);
	cout << endl;
	return 0;
}

Output is:

Normal or Reverse
esreveR ro lamroN

Factorial

#include <iostream>

using namespace std;

int factorial(int n)
{
	if(n == 0 || n == 1) return 1;

	return n * factorial(n-1);
}

int factorial_iter(int n)
{
	int fact = 1;
	for(int i = n; i > 1; i--) {
		fact *= i;
	}
	return fact;
}

int main()
{
	cout << "recursive factorial 10! = " 
			<< factorial(10) << endl;
	cout << "iterative factorial 10! = " 
			<< factorial_iter(10) << endl;
}

With output

recursive factorial 10! = 3628800
iterative factorial 10! = 3628800

We use recursion because it often allows us to express complex algorithms in a compact form, without sacrificing efficiency. As we saw from the example, the recursive implementation of the factorial function obviates the need for local variables. The iterative version has two local variables (fact and i), whereas the recursive version has none. There are usually fewer local variables in a recursive routine than in an iterative routine. The cost of the recursive implementation is borne by the mechanisms in the programming environment that supports function calls, which use the equivalent of a built-in pushdown stack.

Greatest Common Divisors

The following is a compact implementation of Euclid's algorithm for finding the greatest common divisor of two integers. It is base on the observation that the greatest common divisor of two integers m and n with m > n is the same as the greatest common divisor of n and m mod n.

#include <iostream>
using namespace std;

int gcd (int n1, int n2)
{
	if(n2 == 0) return n1;
	cout << "gcd(" << n1 << ',' << n2 <<')'<< endl; 
	return gcd(n2, n1 % n2);
}

int main()
{
	cout << "gcd = " << gcd(1256636, 1630968) << endl;
	return 0;
}

Output from the code is:

gcd(1256636,1630968)
gcd(1630968,1256636)
gcd(1256636,374332)
gcd(374332,133640)
gcd(133640,107052)
gcd(107052,26588)
gcd(26588,700)
gcd(700,688)
gcd(688,12)
gcd(12,4)
gcd = 4

Fibonacci Sequence

#include <iostream>

using namespace std;

int fibo(int n)
{
	return n <= 1 ? n : fibo(n-1) + fibo(n-2);
}

int fibo_iter(int n)
{
	if(n < 0) return -1;  /* error */
	if(n == 0) return 0;
	if(n == 1) return 1;

	int f1 = 1, f2 = 1, f;
	for(int i = 2; i <= n; i++) {
		f = f1 + f2;
		f1 = f2;
		f2 = f;
	}
	return f;
}

int main()
{
	int i;
	int n = 15;
	cout << "recursive Fibonacci " << endl;
	for(i = 0; i < n; i++) 
		cout <<  fibo(i) << " ";
	cout << endl;

	cout << "iterative Fibonacci " << endl;
	for(i = 0; i < n; i++) 
		cout <<  fibo(i) << " ";
	cout << endl;
}

Output is:

recursive Fibonacci
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
iterative Fibonacci
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

Binary Search

This binary search code performs a binary search on a sorted array of integers to find the index of a given integer.

#include <iostream>

using namespace std;

const int LIMITS_REVERSED = -1;
const int NOT_IN_ARRAY = -2;
const int UNSORTED_ARRAY = -3;

int binarySearch(int arr[], int lower, int upper, int target)
{
	if(lower > upper)
		return LIMITS_REVERSED;
	else if(lower == upper && arr[lower] != target)
		return NOT_IN_ARRAY;
	
	if(arr[lower] > arr[upper])
		return UNSORTED_ARRAY;

	int center = (upper - lower)/2 + lower;
	if(target == arr[center])
		return center;
	else if(target < arr[center])
		return binarySearch(arr, lower, center - 1, target);
	else
		return binarySearch(arr, center + 1, upper, target);
}

int binarySearch_iter(int arr[], int lower, int upper, int target)
{
	while(true) {
		if(lower > upper)
			return LIMITS_REVERSED;
		else if(lower == upper && arr[lower] != target)
			return NOT_IN_ARRAY;
		if(arr[lower] > arr[upper])
			return UNSORTED_ARRAY;

		int center = (upper - lower)/2 + lower;
		if(target == arr[center])
			return center;
		else if(target < arr[center])
			upper = center - 1;
		else
			lower = center + 1;
	}
}

void message(int error)
{
	if(error == LIMITS_REVERSED)
		cout << "LIMITS_REVERSED\n";
	else if(error == NOT_IN_ARRAY)
		cout << "NOT_IN_ARRAY\n";
	else if(error == UNSORTED_ARRAY)
		cout << "UNSORTED_ARRAY\n";
	else
		return;
}

int main()
{
	/* sorted array */
	int arr[10] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};

	int target = 17;
	int lower = 0;
	int upper = sizeof(arr) / sizeof(int) -1 ;
	int index;

	index = binarySearch(arr, lower, upper, target);
	message(index);
	if(index >= 0) {
		cout << "Recursive: target is =" << target << endl;
		cout << "arr[" << index << "] = " << arr[index] << endl;
	}

	index = binarySearch_iter(arr, lower, upper, target);
	message(index);
	if(index >= 0) {
		cout << "Iterative: target is =" << target << endl;
		cout << "arr[" << index << "] = " << arr[index] << endl;
	}
	return 0;
}

Output from the run is:

Recursive: target is =17
arr[8] = 17
Iterative: target is =17
arr[8] = 17

String Permutations A

This code computes all permutations of a string.
If our string is abs, the permutations are:
abc, bac, bca, acb, cab, cba .

The following algorithm works this way:

Take out 'a' from "abc".
Now, we have ["bc","cb"].
Insert the 'a' into "bc", so that we have "abc", "bac", and "bca". In the same way, put 'a' into "cb", then we get "acb", "cab", and "cba".

With "abcde", we have following levels of recursion:

before: abcde  (pulling out a) enter: Permutation("bcde")
before: bcde  (pulling out d) enter: Permutation("bce")
before: bce  (pulling out c) enter: Permutation("be")
before: be  (pulling out e) enter: Permutation("b")
before: b  (pulling out b) enter: Permutation ("")
before:   (bottom out)     leave: s = ""
after: b   (adding the b)   leave: s = "b"
after: eb   (adding the e)   leave: s = "eb"
after: ceb   (adding the c)   leave: s = "ceb"
after: dceb   (adding the d)   leave: s = "dceb"
after: adceb   (adding the a)   leave: s = "adceb"

Here is the code:

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<string> permute(string s)
{
	vector<string> permutations;

	if(s.length() == 0) {
		permutations.push_back("");
		return permutations;
	}

	char first = s.at(0);
	string remainder = s.substr(1);
	vector<string> words = permute(remainder);
	string word;
	for(size_t j = 0; j < words.size(); j++) {
		for(size_t i = 0; i <= words[j].length(); i++) {
			word = words[j];
			permutations.push_back(word.insert(i,1,first));
		}
	}
	return permutations;
}

int main()
{
	vector<string> result;
	string str = "abcde";
	
	result = permute(str); 

	for(size_t i = 0; i < result.size(); i++) {
		cout << i << ": " << result[i] << endl;
	}
	return 0;
}

Output is:

0: abcde
1: bacde
2: bcade
3: bcdae
4: bcdea
5: acbde
...
115: aedcb
116: eadcb
117: edacb
118: edcab
119: edcba

String Permutations B

/* String Permutation */

#include <iostream>
using namespace std;

void swap(char* st1, char* st2)
{
	char ch = *st2;
	*st2 = *st1;
	*st1 = ch;
}

int permute(char* str, int start, int end)
{
	if (end - start == 1) {
		cout << str << endl;
	} 
	else {
		for(int i=0; i < end - start; i++) {
			swap(&str[start], &str[start+i]);	
			permute(str, start+1, end);				
			swap(&str[start], &str[start+i]);       
		}
	}
	return 0;
}

int main()
{
	char str[255] = "abc"; 
	permute(str, 0, strlen(str)); 
	return 0;
}

Output is

abc
acb
bac
bca
cba
cab

String Combinations

The following code produces all combinations of a given string. In this example, we're using the term depth of the recursion. It is the maximum degree of nesting of the function calls over the course of the computation.

Generally, the depth will depend on the input. So, when we write a recursive code, we need to take into account that the programming environment has to maintain a pushdown stack of size proportional to the depth of the recursion. Therefore, for a huge problem, we may not be able to resort the recursive approach because of the space needed for stack size.

Data structures build from nodes with pointers are inherently recursive. Linked list, for example, is recursive. So, recursive codes provide natural implementations of many common functions for manipulating such data structures.

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

/* depth: the recursion depth 
	    or the index into the output string of the character 
		that's being generated.  */
/* start: the index of the first of the still available letters */

void combinations(char *input, char *output, 
    int len, int depth, int start)
{
    /* At the current depth, 
	   cycle through the still available letters */

    for( int i = start; i < len; i++ ) {
        output[depth] = input[i];
        combinations(input, output, len, depth+1, i+1);
    }
    output[depth] = '\0';
    cout << output << endl;
}

int main() 
{
    char *input = "abcd";
	char *output = new char[strlen(input) + 1];

	combinations(input, output, strlen(input), 0, 0);
	delete [] output;
}

Output from the run is:

abcd
abc
abd
ab
acd
ac
ad
a
bcd
bc
bd
b
cd
c
d

Subsets of a Set

This code can be summarized as following:

Each element in a set can be in either yes or no state. This means that each subset is a sequence of yes/no, e.g., set with 4 elements, the state can be yes, yes, no, yes.
This gives us 2ⁿ possible subsets.
How can we iterate through all possible sequences of yes/no states for all elements?
If each no can be treated as 0 and each yes can be treated as a 1, then each subset can be represented as a binary string.
Generating all subsets then really just comes down to generating all binary numbers.

/* subsets of a set - recursive */

#include <iostream>
#include <vector>

using namespace std;

vector> getSubsets(vector &set)
{
	vector> allSubsets;

	int max = 1 << set.size();
	for(int i = 0; i < max; i++) {
		vector subset;
		int j = i;
		int index = 0;
		while (j > 0) {
			if((j & 1) > 0) 
				subset.push_back(set[index]);
			j >>= 1;
			index++;
		}
		allSubsets.push_back(subset);
	}
	return allSubsets;
}

int main() 
{
	vector v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	vector> vv;

	vv = getSubsets(v);
	
	for(int i = 0; i < vv.size(); i++) {
		cout << '(';
		for(int j = 0; j < vv[i].size(); j++) {
			cout << vv[i][j] << ' ';
		}
		cout << ')' << endl;
	}

	return 0;
}

Output is:

()
(1 )
(2 )
(1 2 )
(3 )
(1 3 )
(2 3 )
(1 2 3 )
(4 )
(1 4 )
(2 4 )
(1 2 4 )
(3 4 )
(1 3 4 )
(2 3 4 )
(1 2 3 4 )

The recursion is intertwined with the recursively defined structures known as trees. So, we can find additional codes related to recursion from the tree structures:

Binary Tree Example Code

Tower of Hanoi

void tower (int diskCount, int fromPeg, int midPeg, int toPeg)
{
	if(diskCount > 0) {
		tower(diskCount-1, fromPeg, toPeg, midPeg);
		tower(diskCount-1, midPeg, fromPeg, toPeg);
	}
}

Full List of C++ Tutorials