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:

advertisement

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!
advertisement
advertisement

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.

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

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

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

View Answer
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. }

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.