Demonstrate what is meant by recursion

Recursion is a programming technique where a function calls itself directly or indirectly in order to solve a problem. It allows a function to repeat itself several times, reducing the problem size with each iteration, until it reaches a base case where a direct solution can be obtained without further recursion. Recursion is commonly used in problems that can be broken down into smaller, similar subproblems.

Here’s a classic example of recursion: calculating the factorial of a number.

In mathematics, the factorial of a non-negative integer
�
n is denoted by
�
!
n! and is the product of all positive integers less than or equal to
�
n.

The factorial function can be defined recursively as:

\begin{cases}
1 & \text{if } n = 0 \\
n \times (n-1)! & \text{if } n > 0
\end{cases} \]
Let’s implement this factorial function recursively in C:
“`c
#include
// Function prototype
int factorial(int n);
int main() {
int num;
printf(“Enter a non-negative integer: “);
scanf(“%d”, &num);
// Call the factorial function
int result = factorial(num);
printf(“Factorial of %d is %d\n”, num, result);
return 0;
}
// Recursive function to calculate factorial
int factorial(int n) {
// Base case: factorial of 0 is 1
if (n == 0) {
return 1;
}
// Recursive case: n! = n * (n-1)!
else {
return n * factorial(n – 1);
}
}
“`
Explanation of the code:
– `factorial(int n)`: This is the recursive function that computes the factorial of `n`.
– Base Case: `if (n == 0)`: If `n` is 0, the function returns 1 because \( 0! = 1 \).
– Recursive Case: `else`: If `n` is greater than 0, the function recursively calls itself with `n-1` until it reaches the base case.
When you run this program and enter a non-negative integer, the program will compute its factorial using recursion. For example, entering 5 would output:
“`
Enter a non-negative integer: 5
Factorial of 5 is 120
“`

This demonstrates how recursion works by breaking down the factorial calculation into smaller subproblems (calculating `(n-1)!` in each step) until it reaches the base case (factorial of 0).