**Recursive definition:***A definition in which something is defined in terms of a smaller**version of itself.*

From the previous example (factorial), it is clear that:**1. Every recursive definition must have one (or more) base cases.****2. The general case must eventually be reduced to a base case.****3. The base case stops the recursion.**

The concept of recursion in computer science works similarly. Here, we talk about recursive

algorithms and recursive functions. An algorithm that finds the solution to a given problem

by reducing the problem to smaller versions of itself is called a recursive algorithm. The

recursive algorithm must have one or more base cases, and the general solution must

eventually be reduced to a base case.

A function that calls itself is called a recursive function. That is, the body of the

recursive function contains a statement that causes the same function to execute again

before completing the current call. Recursive algorithms are implemented using recursive

functions.

Next, let us write the recursive function that implements the factorial function.**int fact(int num)****{****if (num == 0)****return 1;****else****return num * fact(num – 1);****}**

**cout << fact(3) << endl;**

The output of the previous cout statement is: 6

**To design a recursive function, you must do the following:***1. Understand the problem requirements.**2. Determine the limiting conditions. For example, for a list, the limiting condition**is the number of elements in the list.**3. Identify the base cases and provide a direct solution to each base case.**4. Identify the general cases and provide a solution to each general case in terms of**smaller versions of itself.*

**Tower of Hanoi**

In the nineteenth century, a game called the Tower of Hanoi became popular in Europe.

This game represents work that is under way in the temple of Brahma. At the creation of

the universe, priests in the temple of Brahma were supposedly given three diamond

needles, with one needle containing 64 golden disks. Each golden disk is slightly smaller

than the disk below it. The priests’ task is to move all 64 disks from the first needle to the

third needle. The rules for moving the disks are as follows:**1. Only one disk can be moved at a time.****2. The removed disk must be placed on one of the needles.****3. A larger disk cannot be placed on top of a smaller disk.**

The priests were told that once they had moved all the disks from the first needle to the

third needle, the universe would come to an end.As before, we think in terms of recursion. Let us first consider the case when the first

needle contains only one disk. In this case, the disk can be moved directly from

needle 1 to needle 3. So let us consider the case when the first needle contains only

two disks. In this case, first we move the first disk from needle 1 to needle 2, and

then we move the second disk from needle 1 to needle 3. Finally, we move the first

disk from needle 2 to needle 3. Next, we consider the case when the first needle

contains three disks, and then generalize this to the case of 64 disks (in fact, to an

arbitrary number of disks).

Suppose that needle 1 contains three disks. To move disk number 3 to needle 3, the top

two disks must first be moved to needle 2. Disk number 3 can then be moved from

needle 1 to needle 3. To move the top two disks from needle 2 to needle 3, we use the

same strategy as before. This time we use needle 1 as the intermediate needle.

* *

* *

**Converting a Number from Decimal to Binary using recursion:**

#include <iostream>

using namespace std;

void decToBin(int num, int base);

int main()

{

int decimalNum;

int base;

base = 2;

cout << “Enter number in decimal: “;

cin >> decimalNum;

cout << endl;

cout << “Decimal ” << decimalNum << ” = “;

decToBin(decimalNum, base);

cout << ” binary” << endl;

return 0;

}

void decToBin(int num, int base)

{

if (num > 0)

{

decToBin(num / base, base);

cout << num % base;

}

}

**Sample Run: In this sample run, the user input is shaded.****Enter a number in decimal: 57****Decimal 57 = 111001 binary**