Recursion | Functions

Introduction

Recursion is a programming technique where a function calls itself directly or indirectly. This technique is used to solve problems that can be broken down into smaller, similar subproblems. In C language, recursion is a powerful tool but must be used with caution to avoid infinite loops and stack overflow errors.

How Recursion Works

Recursion typically involves two main components:

Base case: The condition under which the recursion ends. Without a base case, the function would call itself indefinitely.
Recursive case: The part of the function where it calls itself with modified parameters, moving towards the base case.

Example: Factorial Calculation

The factorial of a non-negative integer n is the product of all positive integers less than or equal to n. It is denoted by n!. For example, 5! = 5 * 4 * 3 * 2 * 1 = 120.

Here is a recursive function to calculate the factorial of a number in C:


                    #include <stdio.h>


                    // Function to calculate factorial

                    int factorial(int n) {

                        if (n == 0) // Base case

                            return 1;

                        else

                            return n * factorial(n - 1); // Recursive case

                    }


                    int main() {

                        int num = 5;

                        printf("Factorial of %d is %d", num, factorial(num));

                        return 0;

                    }

Output:
Factorial of 5 is 120

Example: Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. The sequence looks like this: 0, 1, 1, 2, 3, 5, 8, 13, ...

Here is a recursive function to calculate the Fibonacci sequence in C:


                    #include <stdio.h>


                    // Function to calculate Fibonacci number

                    int fibonacci(int n) {

                        if (n <= 1) // Base cases

                            return n;

                        else

                            return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case

                    }


                    int main() {

                        int num = 10;

                        printf("Fibonacci sequence up to %d terms:\\n", num);

                        for (int i = 0; i < num; i++) {

                            printf("%d ", fibonacci(i));

                        }

                        return 0;

                    }

Output:
Fibonacci sequence up to 10 terms:
0 1 1 2 3 5 8 13 21 34

Advantages and Disadvantages of Recursion

Advantages:

Recursion can simplify the code and make it more readable, especially for problems that have a natural recursive structure.
It can reduce the time complexity for certain problems.

Disadvantages:

Recursion can lead to high memory usage because each function call consumes stack space.
It can be less efficient than iterative solutions due to the overhead of multiple function calls.
There is a risk of stack overflow if the base case is not reached or if the problem size is too large.

Conclusion

Recursion is a fundamental concept in programming that allows you to solve complex problems by breaking them down into simpler subproblems. While it can make code more elegant and easier to understand, it is important to use recursion judiciously to avoid potential pitfalls such as stack overflow and excessive memory usage. Understanding the principles of recursion and practicing with different problems will help you become proficient in using this powerful technique.