# Recursion in C Programming Language with Practical Examples

## ¶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 depth-first 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 self-call 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;
}
``````
Output:
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 `(n-1)th` and `(n-2)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;
}
``````
Output:
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.

## ¶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 n-1
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 n-1
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 (n-1)
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 non-negative 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 single-digit 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 {
}

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 (n-1) 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 (n-1) 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;
}
``````