Summary: The following source codes are used in this chapter. The concept of recursion is fundamental in mathematics and computer science. The simple definition is that a recursive program in a programming language is one that calls itself. Another essential component is that there must be a termination condition when the program can cease to call itself.

Recursion explained

1. Power of 2 without recursion

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 4: Recursion

// Calculate the Power of 2 
// Using no recursion 

#include <iostream>
using namespace std;

int power0() { return 1; }
int power1() { return 2 * power0(); }
int power2() { return 2 * power1(); }
int power3() { return 2 * power2(); }

int main() {
   cout << "2 to the 3th is " << power3() << endl;
}

2. Power of 2 using recursion

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 4: Recursion

// Calculate the Power of 2 
// Using recursion

#include <iostream>
using namespace std;

int power(int n) {
   if(n==0) return 1;
   else return 2*power(n-1);
}
int main() {
   cout << "2 to the 3th is " << power(3) << endl;
}

Recursion Usage

1. Decimal to Binary Conversion

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 4: Recursion

// Decimal to Binary Conversion
// Print remainders in reverse order

#include <iostream>
using namespace std;

void bits(int n) {
  if(n){
    bits(n/2);
    cout << n%2;
  }
}

int main() {
  char ch;
  cout << "Convert ASCII code of the character to binary\n" ;
  for(ch = 48; ch < 123; ch++) {
    cout << ch << " - ";
    bits(ch);
    cout << endl;
  }
}

2. Factorial n! = n * (n-1)!, (0! = 1)

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 4: Recursion

// Factorial
// Formula: n! = n * (n-1)!		(0! = 1)

#include <iostream>
using namespace std;

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

int main() {
  unsigned int n;
  cout << "n = "; cin >> n;
  cout << "!n = " << factorial(n) << endl;
}

3. Combinations nCr=n!/r!(n-r)!

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 4: Recursion

// Combination means way of selecting a things or particular item from the group or sets.
// Formula: nCr=n!/r!(n-r)!

#include <iostream>
using namespace std;

int combination(int n, int k) {
  if(k==1) return n;
  else if(n==k) return 1;
  else return combination(n-1, k-1) + combination(n-1, k);
}

int main() {
  int n, k;
  cout << "To calculate combinations, please enter n and k : ";
  cin >> n >> k;
  if (n >=k ) cout << "Combinations: " << combination(n,k) << endl;
  else cout << "n should be greater than or equal to k." << endl;
}

3. Fibonacci numbers

a). Using array and no recursion

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 4: Recursion

// Fibonacci numbers
// Formula: f(n) = f(n-1) + f(n-2),	f(0) = 0, f(1) = 1
// Using array and no recursion

#include <iostream>
using namespace std;

const int MAX = 20;
int fibonacci(int n) {
  int i, F[MAX];
  F[0] = 0;
  F[1] = 1;
  for(i=2; i<=n; i++)
  F[i] = F[i-1] + F[i-2];
  return F[n];
}

int main() {
  int n;
  cout << "n = "; cin >> n;
  if (n < MAX)
    cout << "n-th fibonacci number: " << fibonacci(n) << endl;
  else cout << "Please enter less then " << MAX << ". Please change the value of MAX in the source code." << endl;
}

b). Using variables and no recursion

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 4: Recursion

// Fibonacci numbers
// Formula: f(n) = f(n-1) + f(n-2),	f(0) = 0, f(1) = 1
// Using variables and no recursion

#include <iostream>
using namespace std;

int fibonacci(int n) {
  int f0, f1, f, i;
  f0 = 0;
  f = f1 = 1;
  for (i=2; i<=n; i++) {
    f = f0 + f1;
    f0 = f1;
    f1 = f;
  }
  return n ? f : f0;
}

int  main() {
  int n;
  cout << "n = "; cin >> n;
  cout << "n-th fibonacci number: " << fibonacci(n) << endl;
}

c). Using recursion (variant 1)

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 4: Recursion

// Fibonacci numbers
// Formula: f(n) = f(n-1) + f(n-2),	f(0) = 0, f(1) = 1
// Using recursion (option 1)

#include <iostream>
using namespace std;

int fibonacci(int n) {
  if(n<=1) return n;
  return fibonacci(n-1) + fibonacci(n-2);
}
int main() {
  int n;
  cout << "n = "; cin >> n;
  cout << "n-th fibonacci number: " << fibonacci(n) << endl;
}

d). Using recursion (variant 2)

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 4: Recursion

// Fibonacci numbers
// Formula: f(n) = f(n-1) + f(n-2),	f(0) = 0, f(1) = 1
// Using recursion (option 2)

#include <iostream>
using namespace std;

int fibonacci(int n, int f0=0, int f1=1) {
  if(n<1) return f0;
  else return fibonacci(n-1, f1, f0+f1);
}


int main() {
  int n;
  cout << "n = "; cin >> n;
  cout << "n-th fibonacci number: " << fibonacci(n) << endl;
}

4. Towers of Hanoi

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 4: Recursion

// Towers of Hanoi

#include <iostream>
using namespace std;

void tower(int nDisks, char start, char dest, char spare)
{
  if(nDisks == 1){
    cout << "Move disk from " << start << " to " << dest << endl;
  }
  else {
    tower( nDisks - 1, start, spare, dest );
    cout << "Move disk from " << start << " to " << dest << endl;
    tower( nDisks - 1, spare, dest, start);
  }
}

int main()
{
  int n;
  cout << "\nDisk number: "; cin >> n;
  tower( n, 'A', 'C', 'B' );
}

5. Greatest Common Divisor

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 4: Recursion

// Greatest Common Divisor
// Using recursion

#include <iostream>
using namespace std;

int gcd(int n, int m) {
  if (n%m == 0) return m;
  else return gcd(m,n%m);
}
int main() {
  int n,m;
  cout << "n = "; cin >> n;
  cout << "m = "; cin >> m;
  cout << "gcd = " << gcd(n,m) << endl;
}