What on earth are recursions
Published: 2023-11-22 04:25:50

Recursion in Programming is a problem-solving technique whereby arriving at a problem solution depends on repeatedly solving smaller bits or parts of that problem. This technique can be applied to a wide range of programming areas, ranging from complex data structure to iterative programming. In this article, we'll go through the following:

1. What are recursive functions
2. How to implement recursion
3. In what situations you should implement recursion
4. In what situations you shouldn't implement recursion
5. What distinguishes recursion from iteration

## What are recursive functions?
Recursive functions in programming are functions that directly or indirectly call or invoke itself from within the function body. This type of function can continuously call itself unless a condition is met. This condition is known as the `base` case. A `base` case is used in a recursive function to end or terminate recursive calls or invocation, this is done by specifying a certain condition to be met.
When a `base` case is not specified or set, the function falls into an infinite loop, which can cause stack overflow errors, forcing the program to stop abruptly. Recursive function are similar and behave in the same manner as loops, the advantage it has over loops is that, they can be used to solve complex mathematical problems.

## Types of recursive function

There are two types of recursive functions:
**Direct recursive function:** Direct recursive functions are functions that invoke themselves from their function body
**Indirect recursive function:** indirect recursive functions are function that calls another function from within itself and this function calls back the first or parent function from within itself. For example.


```
functionA()
{
    functionB() /*calling function B*/
    {
        functionA() /*calling back function A*/
    }
}
```

In the example given above, functionA calls functionB from within itself and functionB calls back functionA from within itself. This makes functionA indirectly calls itself.

## How to implement a recursion
The following steps can be regarded as a guide to implementing a recursive function:
**Define the Base case(s):** Identify the simplest instances of the given problem that can be directly solved without further recursion. These are the stopping conditions that prevent the recursion from running into an infinite loop, thereby causing a stack overflow error.
**Define the recursive case:** Write out the function in such a way that it calls itself with a smaller or simpler input.
**Ensure progress towards the base case:** Make sure each recursive call made by the function brings you closer to the base case(s). If this is not the case, the recursion may never terminate.
**Implement the function:** Write the actual code for your recursive function using the base case(s) and recursive case(s).

Here is a simple example in C to illustrate recursion with the calculation of the famous Fibonacci sequence:

```
include <stdio.h>

int fibonacci(int n)
{
    if (n == 0) {
        return (0);
     };
    
    if (n == 1) {
        return (1);
    };
    return (fibonacci(n - 1) + fibonacci(n - 2));
}
int main()
{
    int i;
    
    for (i = 0; i < 15; i++) {
        printf("%d\n", fibonacci(i));
    }

    return (0);
}
```
When the above code is compiled and executed, it produces the following result;

```
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
```

## In what situations you should implement recursion
The recursion problem-solving technique can be useful in situations where a problem can be naturally divided into smaller subparts. Here are some common situations where recursion is often a good choice:
**Mathematical and inductive problems:** Mathematical sequences like Factorials(n!) or the Fibonacci sequence mentioned above are often determined recursively.
**Divide and conquer problems:** Problems that can be broken down into smaller, similar problems.
**Backtracking:** Problems that involves trying out all possible solution and making definitive choices at each step.
**Task decomposition:** Recursion allows you to express the solution to a problem in a clear and concise manner when the problem can easily be divided into smaller, manageable tasks.
**Solving recursive structure:** Recursive functions are also suitable when dealing with data structures or problems that exhibit recursive patterns, such as nested directories or nested data structures.

## In what situations you shouldn't implement recursion
While implementing a recursive function can seem really cool, there are situations where it might not be the best choice or where it could lead to practical challenges. Here are some situations where you might want to avoid implementing a recursive function:
**Memory usage:** Each recursive call made adds a new frame to the call stack. In situations where memory usage is a critical concern, recursion might not be the best option.
**Deep recursion:** Deep recursion, where the number of recursive calls is large, it can easily lead to stack overflow errors. This can be a setback in some programming environments, and it might be more practical to use an iterative solution or optimize the recursive algorithm.
**Readability and maintainability:** Recursive solutions can be elegant, but they are not always the most readable or easily maintainable. In some cases, an iterative solution might be more straightforward and easier for others to understand.
**Limited language support:** Some programming languages may not handle recursion well, or they may not optimize tail-recursive functions, leading to potential performance issues.
**Complex state management:** Recursive solutions might not be suitable for problems that require complex state management, as passing and managing states through recursive calls can be challenging.

In a situation where you find yourself deliberating whether to use recursion in solving a particular problem, it is essential you evaluate the pros and cons of recursion. In many cases, the choice between recursion and iteration depends on the specific requirements of the problem, the nature of the input data, and the constraints of the programming environment.

## What distinguishes recursion from iteration
Recursion and iteration are two different approaches to solving problems in programming, and they involve different control flow mechanisms. Some of the key differences are:
**Control flow mechanisms:** Recursion relies on function calls and the call stack to manage control flow, while iteration uses explicit loops to control the flow.
**Memory usage:** Recursion can use more memory due to the call stack, which grows with each recursive call. Iteration typically uses a constant amount of memory.
**Readability:** Recursion can be more elegant and in certain cases can lead to more readable code. Iteration can be more straightforward and may be preferred for simple sequential tasks.
**Performance:** The performance of recursion and iteration can vary based on the problem and the programming language. In some cases, iterative solutions may be more efficient.

Choosing between recursion and iteration often depends on the nature of the problem, the programming language, and considerations such as readability and performance.

## Conclusion
In conclusion, we have looked at recursion, a very powerful programming problem-solving technique used in solving a wide range of problems. This technique involves solving a problem by breaking it down into manageable parts. Also, how to implement recursive functions, which situations are best suited to use recursive functions and which situations are not, and lastly, what differentiates a recursion from an iteration. thoroughly going through the aforementioned will give you a good grasp on recursion.
In addition, I am currently available and actively seeking opportunities as a technical writer, with a good background in C and Python, I am open to projects that demand clarity and a deep understanding of complex technical concepts. Kindly reach out to me via email at ebirikele@gmail.com and on[ Linkedin](https://www.linkedin.com/in/kelechi-ebiri-3b25ba229/)