In 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 <stdio.h> long int factorial(int n); int main() { int n; printf("Enter a number to find factorial: "); scanf("%d", &n); printf("Factorial of %d = %ld", n, factorial(n)); return 0; } long int factorial(int n) { if (n >= 1) return n*factorial(n-1); else return 1; } |
OUTPUT
1 | Enter a number to find factorial: 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 27 | #include<stdio.h> int fibonacci(int); int main() { int n, i = 0, c; printf("Enter the nth number in fibonacci series "); scanf("%d", &n); printf("\n Fibonacci series terms are:\n"); for (c = 1; c <= n; c++) { printf("%d\n", fibonacci(i)); i++; } return 0; } int fibonacci(int n) { if (n == 0 || n == 1) return n; else return (fibonacci(n-1) +fibonacci(n-2)); } |
1 2 3 4 5 6 7 8 9 10 11 12 13 | Enter the nth number in fibonacci series 10 Fibonacci series terms are: 0 1 1 2 3 5 8 13 21 34 |