C Programming
Recursion in C Programming Language with Practical Examples
 What is Recursion in Computer Science
 Recursion basics in C programming
 Designing Recursive Functions
 Recursive Function for nth Fibonacci
 Control flow in a recursive call
 Recursion Flow

Practical Problems of Recursion in C Programming
 Example 1: Write a recursive function to print numbers from 1 to n
 Example 2: Write a recursive function to print numbers from 1 to n in reverse order
 Example 3: Write a recursive function to calculate n! (nth factorial)
 Example 4: Write a recursive function to calculate the sum of digits of n.
 Example 5: Write a recursive function to find the gcd of two numbers.
 Example 6: Write a recursive function to implement binary search recursively.
 Example 7: Write a recursive function to solve the problem Towers of Hanoi.
 Run C Programming Online Compiler
¶What is Recursion in Computer Science
Recursion is one of the core concepts in computer science, serving as a building block for solving numerous problems including depthfirst search, merge sort, Towers of Hanoi, tree traversals, recursive dynamic programming, and many others.
Understanding recursion requires basic knowledge of functions, which we have already covered. Before diving into recursion, refresh your basic understanding of functions from Functions in C Programming.
¶Recursion basics in C programming
In recursion, a function solves a problem by calling itself with a smaller version of that problem. This selfcall can happen directly within the function body or indirectly through a chain of calls involving other functions, eventually leading back to the original function.
#include<stdio.h>
int numberSum(int n)
{
// returns sum of integers from 1 to n
if (n <= 0) return 0; // base case
return n + numberSum(n  1); // recursive call
}
int main()
{
int sum = numberSum(5);
printf("sum = %d", sum);
return 0;
}
sum = 15
Here, the function numberSum()
makes a recursive call to itself in the process of calculating the summation of integer numbers from 1 to n.
When a function calls itself recursively it’s important to set a terminating condition to tell the function when to stop or it will keep going forever. This terminating condition in a function is known as the base case. Here, we used if (n <= 0)
as the base case.
¶Designing Recursive Functions
To design a recursive function, we need to carefully consider the following two building blocks of a recursive function, the base case and recursive case.
¶Identify the base case
The base case is the smallest unit that the function can handle on its own, without needing to break it down further. It serves as the terminating point where the recursion ends, providing a solution and returning control to the calling function. A function may have more than one base case depending on what problem we are solving.
¶Identify the recursive case
We call a recursive function again with slightly modified data in a recursive call. So, it’s important to identify how the problem can be broken down into smaller versions of itself. There may be more than one recursive call from a function each with a smaller version of the problem.
¶Recursive Function for nth Fibonacci
At first, we identify the base cases and recursive cases. The 0th
and 1st
Fibonacci numbers are 0 and 1, serving as base cases since we do not need to break them down further. The nth Fibonacci number depends on the (n1)th
and (n2)th
Fibonacci numbers. We make recursive calls on them to calculate our answer.
#include<stdio.h>
int nth_fib(int n)
{
// returns nth fibonacci number
if (n == 0) return 0; // base case fib(0) = 0
if (n == 1) return 1; // base case fib(1) = 1
return nth_fib(n  1) + nth_fib(n  2); // recursive case
}
int main()
{
int fib = nth_fib(10);
printf("10th Fibonacci Number = %d", fib);
return 0;
}
10th Fibonacci Number = 55
¶Control flow in a recursive call
In C programming language, code is executed sequentially, line by line, unless there are control flow statements that alter this flow. When a function is called, the control flow moves to that function, does its job, and then comes back to where the function was called. In the previous example, when the function numberSum()
is called, it calculates the sum and then returns it to print in the next line.
For a better understanding of recursion, we have to understand what exactly happens when a function is called. We can break down the recursive control flow as follows,
¶Function Call
When a function is called, a stack frame is created on the call stack. This frame stores the function’s local variables, argument values, and the return address of control. After the function completes its task, the stack frame is removed, and the control returns to its previous place from where the function was called. An operating system provides a program with limited stack memory to execute. In some cases, a program may enter into an infinite recursive call, using up all the allocated stack memory. Therefore, when the program attempts to allocate more memory, a stack overflow occurs, leading to the termination of the program.
¶Recursive Call
In recursion, each recursive call adds a new stack frame above the previous one storing functions current instance locals. In the previous example, when we call numberSum(5)
, it creates a stack frame with n = 5
. Then, it makes a recursive call to numberSum(4)
, creating another stack frame with n = 4
above it. When the calculation is complete, the stack frame for numberSum(4)
is removed, and the control returns to numberSum(5)
. This process continues until all recursive calls are completed.
¶Base Case
Once the base case is met, no more recursive calls occur for that instance of the function. Thus returning some value and removing the stack frame. In the example, we have seen if (n <= 0)
as the base case. Whenever the function encounters this condition it returns the value 0
as well as returns the control to the caller function.
¶Recursion Flow
¶Practical Problems of Recursion in C Programming
¶Example 1: Write a recursive function to print numbers from 1 to n
#include <stdio.h>
// Recursive function to print numbers from 1 to n
void printNumbers(int n) {
// Base case: stop recursion when n becomes 0
if (n == 0) {
return;
}
// Print the current number
printf("%d ", n);
// Recursive call to printNumbers with n1
printNumbers(n  1);
}
int main() {
int n;
// Input: Get the value of n from the user
printf("Enter the value of n: ");
scanf("%d", &n);
// Call the recursive function to print numbers from 1 to n
printf("Numbers from 1 to %d are: ", n);
printNumbers(n);
return 0;
}
¶Example 2: Write a recursive function to print numbers from 1 to n in reverse order
#include <stdio.h>
// Recursive function to print numbers from 1 to n in reverse order
void printNumbersReverse(int n) {
// Base case: stop recursion when n becomes 0
if (n == 0) {
return;
}
// Recursive call to printNumbersReverse with n1
printNumbersReverse(n  1);
// Print the current number after the recursive call (in reverse order)
printf("%d ", n);
}
int main() {
int n;
// Input: Get the value of n from the user
printf("Enter the value of n: ");
scanf("%d", &n);
// Call the recursive function to print numbers from 1 to n in reverse order
printf("Numbers from 1 to %d in reverse order are: ", n);
printNumbersReverse(n);
return 0;
}
¶Example 3: Write a recursive function to calculate n! (nth factorial)
#include <stdio.h>
// Recursive function to calculate n!
unsigned long long factorial(int n) {
// Base case: factorial of 0 is 1
if (n == 0) {
return 1;
}
// Recursive call to calculate factorial of (n1)
return n * factorial(n  1);
}
int main() {
int n;
// Input: Get the value of n from the user
printf("Enter the value of n: ");
scanf("%d", &n);
// Check if n is a nonnegative integer
if (n < 0) {
printf("Factorial is not defined for negative numbers.\n");
} else {
// Call the recursive function to calculate n!
printf("Factorial of %d is: %llu\n", n, factorial(n));
}
return 0;
}
¶Example 4: Write a recursive function to calculate the sum of digits of n.
#include <stdio.h>
// Recursive function to calculate the sum of digits of n
int sumOfDigits(int n) {
// Base case: return n if it's a singledigit number
if (n < 10) {
return n;
}
// Recursive call to sum the digits of n
return n % 10 + sumOfDigits(n / 10);
}
int main() {
int n;
// Input: Get the value of n from the user
printf("Enter the value of n: ");
scanf("%d", &n);
// Call the recursive function to calculate the sum of digits of n
printf("Sum of digits of %d is: %d\n", n, sumOfDigits(n));
return 0;
}
¶Example 5: Write a recursive function to find the gcd of two numbers.
#include <stdio.h>
// Recursive function to calculate the gcd of two numbers
int gcd(int a, int b) {
// Base case: gcd(a, 0) is a, and gcd(0, b) is b
if (b == 0) {
return a;
}
// Recursive call to calculate gcd
return gcd(b, a % b);
}
int main() {
int num1, num2;
// Input: Get the values of num1 and num2 from the user
printf("Enter the first number: ");
scanf("%d", &num1);
printf("Enter the second number: ");
scanf("%d", &num2);
// Call the recursive function to calculate the gcd
printf("GCD of %d and %d is: %d\n", num1, num2, gcd(num1, num2));
return 0;
}
Example with Algorithm and details
¶Example 6: Write a recursive function to implement binary search recursively.
#include <stdio.h>
// Recursive function to perform binary search
int binarySearchRecursive(int arr[], int low, int high, int target) {
// Base case: if the search space is empty, target is not in the array
if (low > high) {
return 1;
}
// Calculate the middle index
int mid = low + (high  low) / 2;
// Check if the target is equal to the element at the middle index
if (arr[mid] == target) {
return mid;
}
// If the target is smaller, search in the left half
else if (arr[mid] > target) {
return binarySearchRecursive(arr, low, mid  1, target);
}
// If the target is larger, search in the right half
else {
return binarySearchRecursive(arr, mid + 1, high, target);
}
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int target;
// Input: Get the target value from the user
printf("Enter the target value: ");
scanf("%d", &target);
// Call the recursive function to perform binary search
int result = binarySearchRecursive(arr, 0, n  1, target);
// Output: Print the result
if (result != 1) {
printf("Element %d found at index %d.\n", target, result);
} else {
printf("Element %d not found in the array.\n", target);
}
return 0;
}
¶Example 7: Write a recursive function to solve the problem Towers of Hanoi.
#include <stdio.h>
// Function to move a disk from source peg to destination peg
void moveDisk(int disk, char source, char destination) {
printf("Move disk %d from peg %c to peg %c\n", disk, source, destination);
}
// Recursive function to solve Towers of Hanoi
void towersOfHanoi(int n, char source, char auxiliary, char destination) {
// Base case: If there's only one disk, move it from source to destination
if (n == 1) {
moveDisk(n, source, destination);
return;
}
// Move (n1) disks from source to auxiliary peg using destination peg
towersOfHanoi(n  1, source, destination, auxiliary);
// Move the nth disk from source to destination peg
moveDisk(n, source, destination);
// Move the (n1) disks from auxiliary peg to destination peg using source peg
towersOfHanoi(n  1, auxiliary, source, destination);
}
int main() {
int numDisks;
// Input: Get the number of disks from the user
printf("Enter the number of disks: ");
scanf("%d", &numDisks);
// Call the recursive function to solve Towers of Hanoi
towersOfHanoi(numDisks, 'A', 'B', 'C');
return 0;
}
Hope, the above Recursive Examples will help you clear your concepts about Recursion in C programming very easily.
¶Run C Programming Online Compiler
To make your learning more effective, exercise the coding examples in the text editor below.
Arrays in C Programming  Algorithm and Practical examples
Structure in C Programming Language with practical examples
All Tutorials in this playlist
Popular Tutorials
Categories

Artificial Intelligence (AI)
11

Bash Scripting
1

Bootstrap CSS
0

C Programming
14

C#
0

ChatGPT
1

Code Editor
2

Computer Engineering
3

CSS
28

Data Structure and Algorithm
18

Design Pattern in PHP
2

Design Patterns  Clean Code
1

EBook
1

Git Commands
1

HTML
19

Interview Prepration
2

Java Programming
0

JavaScript
12

Laravel PHP Framework
37

Mysql
1

Node JS
1

Online Business
0

PHP
28

Programming
8

Python
12

React Js
19

React Native
1

Redux
2

Rust Programming
15

SEO  Search Engine Optimization
1

Tailwind CSS
1

Typescript
10

Uncategorized
0

Vue JS
1

Windows Operating system
1

Woocommerce
1

WordPress Development
2
Tags
 Artificial Intelligence (AI)
 Bash Scripting
 Business
 C
 C Programming
 Csharp programming
 C++
 Code Editor
 Computer Engineering
 CSS
 Data Structure and Algorithm
 Database
 Design pattern
 Express JS
 git
 Git Commands
 github
 HTML
 Java
 JavaScript
 Laravel
 Mathematics
 MongoDB
 Mysql
 Node JS
 PHP
 Programming
 Python
 React Js
 Redux
 Rust Programming Language
 SEO
 TypeScript
 Vue JS
 Windows terminal
 Woocommerce
 WordPress
 WordPress Plugin Development