Theory of Computation - Recursion Definition and Examples

Recursion is a very important concept in computer science. Many problems can be simplified by the use of recursion. A formal definition of recursion is – 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.

View Answer

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;
```
```
}
```

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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.

View Answer

The Tower of hanoi can be solved by recursive procedure by reducing the problem into the following sub-problems:

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.

« Prev - Theory of Computation – Basic Definitions

» Next - Theory of Computation – Regular Expressions and Regular Languages

Related Posts:

Recommended Articles: