C++ Tutorial Quiz - Recursion - 2020

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.

Unlike repetitive/conditional cases, recursion is not a concept that comes up in daily life. Because it is unfamiliar, learning how to use recursion can be tough, and reaching a certain level of understanding takes a considerable time and practices. However, learning how to use recursion is worth the effort. Recursion, as a problem solving tool, can be so powerful that it sometimes seems almost magical, and using recursion makes it possible to write otherwise complicated programs in very simple and elegant way.

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.

The typical recursive coding takes the following form:

if (test for simple case) {
    return (simple computation without recursion);
} else {
    return (recursive solution);
}

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 while a looping structure is the main control structure in an iterative 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.

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

#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 f[100] = {0};

int factorial_dynamic(int n)
{
	if(f[n]) return f[n];
	if(n == 0 || n == 1) {
		f[n] = 1;
		return f[n];
	}	
	f[n] = n*factorial(n-1);
	return f[n];
}

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.

#include <iostream>

using namespace std;

int n_to_the_kth_power(int n, int k)
{
	if (k == 0) 
		return 1;
	else 
		return n * n_to_the_kth_power(n, k-1);
}

int main ()
{

  int n = 2, k = 10;
  while (k >= 0) {
	  cout << n << "**" << k << " = " << n_to_the_kth_power(n,k) << endl; 
	  k--;
  }
  while(1) {}
  return 0;
}

The output is:

2**10 = 1024
2**9 = 512
2**8 = 256
2**7 = 128
2**6 = 64
2**5 = 32
2**4 = 16
2**3 = 8
2**2 = 4
2**1 = 2
2**0 = 1

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 m, int n)
{
	if(n == 0) return m;
	cout << "gcd(" << m << ',' << n <<')'<< endl; 
	return gcd(n, m % n);
}

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

Iterative code:

int gcd_iterative(int m, int n)
{
	int temp;
	while(n != m % n) {
	    temp = n;
	    n = m % n;
	    m = temp;
	    if(n == 0) return m;
	}
	return m;
}

#include <iostream>

using namespace std;

const int M1 = 3, N1 = 2;  // matrix A
const int M2 = 2, N2 = 4;  // matrix B

// iterativie

void matmul(int a[][N1], int b[][N2], int c[][N2])
{
	for(int i = 0; i < M1; i++) {
		for(int j = 0; j < N2; j++) {
			for(int k = 0; k < N1; k++) {
				c[i][j] = c[i][j] + a[i][k]*b[k][j];
			}
		}
	}
}


// recursive

void matmulr(int a[M1][N1], int b[M2][N2], int c[M1][N2])
{
	static int i = 0, j = 0, k = 0;
	if(i < M1) {
		if(j < N2) {
			if(k < N1) {
				c[i][j] += a[i][k]*b[k][j];
				k++;
				matmulr(a,b,c);
			}
			k = 0;
		        j++;
			matmulr(a,b,c);
		}
		j = 0;
		i++;
		matmulr(a,b,c);
	}
}

int main()
{
	int a[M1][N1] = {{1,2},
	                 {3,4},
	                 {5,6}};

	int b[M2][N2] = {{1,2,3,4},
		         {5,6,7,8}};

	int c[M1][N2] = {0};

	matmul(a, b, c);    // iterative
	matmulr(a, b, c);   // recursive

	/* C = {{11,14,17,20}, 
	        {23,30,37,44}, 
		{35,46,57,68}} */
	 	
	return 0;
}

The complexity is O(n^3), however, there is another algorithm called Strassen's subcubic algorithm which gives O(n^2.8) complexity.

Below are the pictures showing what's happening when we use recursive algorithm. Since the recursive algorithm is doing the same calculation repeatedly it becomes slow when it does those recalculation so many times. So, we need to do dynamic programming where the pre-computed values are saved and used in later calculations.

Pictures are from Recursion and Dynamic Programming

As we can see from the pictures, the advantage of using dynamic programming approach over simple recursive algorithm is clear.

The following code shows three ways of calculating Fibonacci sequence: simple recursive, iterative, and dynamic programming:

#include <iostream>
using namespace std;

int fibo(int n)
{
	if(n == 0 || n == 1) return n;
	return fibo(n-1)+fibo(n-2);
}

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

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

int fibo_dynamic(int n)
{
        static int saved[100] = {0};

	if(saved[n] != 0) return saved[n];

	if(n == 0 || n == 1) {
		saved[n] = n;
		return saved[n];
	}

	saved[n] = fibo_dynamic(n-1)+fibo_dynamic(n-2);

	return saved[n];
}

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_iter(i) << " ";
	cout << endl;

	cout << "dynamic Fibonacci " << endl;
	for(i = 0; i < n; i++) 
		cout <<  fibo_dynamic(i) << " ";
	cout << endl;

	return 0;
}
 

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
dynamic Fibonacci
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

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

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:

1. Take out 'a' from "abc".
2. Now, we have ["bc","cb"].
3. 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 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

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

This code can be summarized as following:

1. 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.
2. 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.
3. 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:

1. Binary Tree Example Code

#include <iostream>
using namespace std;

void tower(int a, char from, char buf, char to){
    if(a==1) {
       cout << "Move disc 1 from " << from<< " to "<< to << "\n";
       return;
    }
    else {
       tower(a-1, from, to, buf);
       cout << "Move disc " << a << " from "<< from << " to "<< to << "\n";
       tower(a-1, buf, from, to);
    }
}

int main()
{
     tower(3, 'A', 'B', 'C');
     return 0;
}

Output:

Move disc 1 from A to C
Move disc 2 from A to B
Move disc 1 from C to B
Move disc 3 from A to C
Move disc 1 from B to A
Move disc 2 from B to C
Move disc 1 from A to C

Given three rods and $n$ disks, the sequence $S_1 = \{a_k\}$ giving the number of the disk ($i=1$ to $n$) to be moved at the $k$th step is given by the remarkably simple recursive procedure of starting with the list $S_1 = \{1\}$ for a single disk, and recursively computing $$S_n = \{S_{n-1}, n, S_{n-1}\}.$$ For the first few values of $n$, this gives the sequences shown in the following table. A solution of the three-rod four-disk problem is illustrated above. The sequence represents the disk on the move:

The property of the sequence is discussed in
http://mathworld.wolfram.com/TowerofHanoi.html.

Finding a path from (0,0) to (M,N) and there are some grid points not allowed to visit.

#include <iostream>
#include <vector>
#include <map>

using namespace std;

const int  M = 5, N = 4;

class Point
{
	int x, y;
public:
	Point(int a, int b) : x(a), y(b) {}
	int getX() { return x;}
	int getY() { return y;}
};

bool isFree(int x, int y)
{
	if(x == 0 && y == 1) return false;
	if(x == M-1 && y == N-1) return false;
	return true;
}

bool getPath(int x, int y, vector<Point*>& path, map<Point*, bool>& pMap)
{
	bool go = false;
	Point *p = new Point(x,y);
	if(x == 0 && y == 0) return true;
	if(x >= 1 && !pMap[p] && isFree(x,y)) go = getPath(x-1,y, path, pMap);
	if(!go && y >= 1 && !pMap[p] && isFree(x,y)) go = getPath(x,y-1, path, pMap);
	if(go && isFree(x,y)) {
		path.push_back(p);
		pMap.insert(make_pair(p, true));
	}
	return go;
}

int main()
{
	vector<Point *> path;
	map<Point *, bool> pMap;
	getPath(M, N, path, pMap);
	for(int i = 0; i < path.size(); i++) 
		cout << path[i]->getX() << "," << path[i]->getY() << endl;

	return 0;
}

Output:

1,0
1,1
1,2
1,3
1,4
2,4
3,4
4,4
5,4

For more on dynamic programming, please visit Algorithms - Dynamic Programming.

The following code print elements of a linked list in reverse order (from tail to head)

#include 
using namespace std;

typedef struct node
{
	int data;
	node* next;
} node;

class List
{
public:
	List(node* n = 0):head(n){}
	void addNode(int d);
	void print();
	void reverse_print(node *);
	node* getHead() {return head;}
private:
	node* head;
};

void List::addNode(int d)
{
	if(head == 0) {
		head = new node;
		head->data = d;
		head->next = 0;
		return;
	} 

	node* ptr = head;

	while(ptr) {
		if(ptr->next == 0) {
			ptr->next = new node;
			ptr->next->data = d;
			ptr->next->next = 0;
			break;
		}
		ptr = ptr->next;
	}
}

void List::print()
{
	node* ptr = head;
	while(ptr) {
		cout << ptr->data << " ";
		ptr = ptr->next;
	}
	cout << endl;
}

void List::reverse_print(node *ptr)
{
	if(ptr == 0) return;

	reverse_print(ptr->next);
	cout << ptr->data << " ";
}

int main()
{
	List L = List();
	L.addNode(1);L.addNode(2);L.addNode(3);L.addNode(4);L.addNode(5);
	L.print();
	L.reverse_print(L.getHead());
}

Output:

1 2 3 4 5 
5 4 3 2 1

With recursive approach, we may have stack overflow issue. That's where we use another approach, tail recursion:

Tail Recursion:

def fact(n, current_fact=1):
    if n == 1:
        return current_fact
    else:
        return fact(n-1, current_fact*n)

Compare the code above with the normal recursive algorithm:

Normal Recursion:

def fact(n):
    if n == 1:
        return n
    else:
        return n*fact(n-1)

Here is the steps that actually happening in tail recursive:

fact(4, 1)
return fact (3,  1 * 4 )  //n == 4
return fact (2,  4 * 3 )  //n == 3
return fact (1,  12 * 2 ) //n == 2
return 24                 //n == 1

In tail recursive, each function call carries current factorial value. So, the final(tail) function call has the result.

Compare the above with the steps for normal recursive calls:

(fact  4)
(4 * (fact  3))
(4 * (3 * (fact  2)))
(4 * (3 * (2 * (fact  1))))
(4 * (3 * (2 (* 1))))
(4 * (3 * (2)))
(4 * (6))
24