In a C programming language, a function that calls itself is known as a recursive function.
And, this technique is called as recursion.
Recursive functions are very useful to solve many problems such as Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc.
How recursion works?
1 2 3 4 5 6 7 8 9 10 11 12 13 | void recurse() { ... .. ... recurse(); ... .. ... } int main() { ... .. ... recurse(); ... .. ... } |
Example: Write a program in a C++ language to find the factorial using recursion.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | #include <iostream> using namespace std; int factorial(int n); int main() { int n; cout << "Enter a number to find factorial: "; cin >> n; cout << "\nFactorial of " << n << " is= " << factorial(n); return 0; } int factorial(int n) { if (n >= 1) return n * factorial(n - 1); else return 1; } |
Output
1 2 3 | Enter a number to find factorial: 5 // enter by user Factorial of 5 = 120 |
Example: Write a program in a C language to print the Fibonacci series using recursion.
Fibonacci series are 0, 1, 1, 2, 3, 5, 8, …,.
In fibonacci series, except for the first two terms of the series, every other term is the sum of the previous two terms, for example, 5 = 2 + 3.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | #include <iostream> using namespace std; int fibonacci(int); int main() { int n, i = 0, c; cout << "Enter the nth number in fibonacci series "; cin >> n; cout << "\n Fibonacci series terms are:\n"; for (c = 1; c <= n; c++) { cout << " " << fibonacci(i); i++; } return 0; } int fibonacci(int n) { if (n == 0 || n == 1) return n; else return (fibonacci(n - 1) + fibonacci(n - 2)); } |
Output
1 2 3 4 | Enter the nth number in fibonacci series 7 // enter by user Fibonacci series terms are: 0 1 1 2 3 5 8 13 21 34 |