*A function that calls itself directly or indirectly and terminates after a finite number of steps.*

So that the program does not continue to run indefinitely, a well-defined recursive function should have the following properties:

- There must be a
*base criteria*for which the function does not call itself. - With every call to itself the function must be closer to the base criteria.

For example a factorial can be defined recursively as:

factorial(x) = x * factorial(x – 1) for x > 1

= 1 for x = 1 or x = 0

The base criteria for the function is at x = 1 or x = 0 .i.e. the function does not call itself when it reaches x = 1 or x = 0.The function calls itself whenever x is not 1 or 0 and moves closer to the base criteria as x is reduced at every recursive call.

Below are few programming questions based on recursion.

**Question 1: **

Fibonacci Sequence is recursively defined as

if n = 0 or n = 1, then F(n) = n

if n > 1, then F(n) = F(n – 2) + F(n – 1)

The sequence is as follows : 1, 1, 2, 3, 5, 8, 13, 21, ……

**Write a program to output the sequence for n numbers of terms.**

Here is source code of the C++ Program to print out the Fibonacci series. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

`/*`

`* C program to print out the fibonacci series`

`*/`

`#include <iostream>`

using namespace std;

int fibo(int n) {

if (n == 0 || n == 1)

return 1;

`else`

return (fibo(n - 2) + fibo(n - 1));

`}`

int main() {

int n;

cout << "Enter the number of terms for the series: ";

cin >> n;

for (int i = 0; i <= n; i++ )

cout << fibo(i) << " ";

return 0;

`}`

Output: Enter the number of terms for the series: 10 1 1 2 3 5 8 13 21 34 55 89

**Question 2:**

Tower of hanoi problem:

Suppose three pegs labelled A, B and C are given, and suppose there are finite number n of disks with decreasing size placed on peg A. The objective of the game is to move the disks from peg A to peg C using peg B as an auxiliary.

The rules of the games are as follows:

- Only one disk may be moved at a time. Specifically, only the top disk on any peg may be moved to any other peg.
- At no time can larger disk be placed on a smaller disk.

X->Y denotes “Move top disk from peg X to peg Y” where X and Y may be any of the three pegs.

**Write a recursive program to generate a solution for the Tower of Hanoi problem for n number of disks.**

- Move the top n – 1 disks from peg A to peg B.
- Move the top disk from peg A to Peg C: A->C.
- Move the top n – 1 disks from peg B to peg C.

Here is source code of the C++ Program to solve Tower of Hanoi problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

`/*`

`* Tower of Hanoi problem for n disks`

`*/`

`#include <iostream>`

using namespace std;

void Tower(int n, char beg, char aux, char end) {

if (n == 1) {

cout << beg << "->" << end << endl;

`}`

else {

Tower(n - 1, beg, end, aux);

cout << beg << "->" << end << endl;

Tower(n - 1, aux, beg, end);

`}`

`}`

int main() {

int n;

cout << "Enter the number of disks for the problem: ";

cin >> n;

Tower(n, 'A', 'B', 'C');

return 0;

`}`

Output: Enter the number of disks for the problem: 3 A->C A->B C->B A->C B->A B->C A->C

**Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.**

If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.