# 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:

1. There must be a base criteria for which the function does not call itself.
2. 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:

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

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.

1. `/*`
2. ` * C program to print out the fibonacci series`
3. ` */`
4. `#include <iostream>`
5. `using namespace std;`
6. ` `
7. `int fibo(int n) {`
8. `    if (n == 0 || n == 1)`
9. `        return 1;`
10. `    else`
11. `        return (fibo(n - 2) + fibo(n - 1));`
12. `}`
13. `int main() {`
14. `    int n;`
15. `    cout << "Enter the number of terms for the series: ";`
16. `    cin >> n;`
17. `    for (int i = 0; i <= n; i++ )`
18. `        cout << fibo(i) << " ";`
19. `    return 0;`
20. `}`

```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:

1. Only one disk may be moved at a time. Specifically, only the top disk on any peg may be moved to any other peg.
2. 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.

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

1. Move the top n – 1 disks from peg A to peg B.
2. Move the top disk from peg A to Peg C: A->C.
3. 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.

1. `/* `
2. ` * Tower of Hanoi  problem for n disks	`
3. ` */`
4. `#include <iostream>`
5. `using namespace std;`
6. ` `
7. `void Tower(int n, char beg, char aux, char end) {`
8. `    if (n == 1) {`
9. `        cout << beg << "->" << end << endl;`
10. `    }`
11. `    else {`
12. `        Tower(n - 1, beg, end, aux);`
13. `        cout << beg << "->" << end << endl;`
14. `        Tower(n - 1, aux, beg, end);`
15. `    }`
16. `}`
17. `int main() {`
18. `    int n;`
19. `    cout << "Enter the number of disks for the problem: ";`
20. `    cin >> n;`
21. `    Tower(n, 'A', 'B', 'C');`
22. `    return 0;`
23. `}`

```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. 