Understanding The Recursion

In computer science, recursion is a method of solving a computational problem in which the solution is dependent on solutions to smaller instances of the same problem. The approach is suitable for a wide range of problems, and recursion is one of the core principles of computer science.

When a function is defined in such a way that it calls itself, it is regarded as a recursive function.

What is need for the recursion

Iterations such as the for loop and while loop can also be used to create a function that calls itself repeatedly. So you may be wondering why we require recursion in the first place.

A common algorithm design strategy is to break a problem down into sub-problems of the same type as the original, solve those sub-problems, and then combine the results. This is widely recognized as the divide-and-conquer method.

Recursion is one of the ways, how we can emulate the divide-and-conquer method. It is an effective tool for dividing larger problems into smaller subproblems. Recursive functions are also more pretty and readable than iterative functions.

Along with the divide-and-conquer method, recursion is widely utilized by many traditional programming algorithms such as,

1. Tower of Hanoi
2. Merge Sort
3. Quick Sort
4. Tree traversal (BFS and DFS)

How to implement recursion in python

Consider a classic example of calculating a factorial of a number. If one has to write the function using a loop it would look like the below:

def factorial_using_loop(num):
    factorial = 1
    for i in range(1, num+1):
        factorial *= i
    return factorial

num = 5
print(f"Factorial of {num} is => {factorial_using_loop(num)}")

# Output: Factorial of 5 is => 120

Now let us see how it will look like if we use a recursive function,

def factorial_using_recursion(num):
    if num == 0 or num == 1:
        return 1
    else:
        return num * factorial_using_recursion(num-1)

num = 5
print(f"Factorial of {num} is => {factorial_using_recursion(num)}")
# Output: Factorial of 5 is => 120

In this example, when num equals 0 or 1, functions returns 1. This is known as the base case, which is a condition whose output can be obtained without the need for recursion. The recursive case is when the num is greater than 1 then functions returns num multiplied by the factorial of num-1

Another popular use case for recursion is computing a Fibonacci series. This is how we can write the code to compute Fibonacci series for first 10 numbers,

def fibonacci_using_recursion(num):
    if num <= 0:
        return []
    elif num == 1:
        return [0]
    elif num == 2:
        return [0, 1]
    else:
        return fibonacci_using_recursion(num-1) + [fibonacci_using_recursion(num-1)[-1] + fibonacci_using_recursion(num-2)[-1]]
print(fibonacci_using_recursion(10))
# Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Comparing recursion with iterative functions

In Python, recursion, for loops, and while loops are all ways to control the flow of a programme, but they are used in slightly different ways.

Let us see how they compare in terms of memory consumption and execution speed.

Memory Consumption

Each time a recursive function is called, a new stack frame is created, using memory, making recursion potentially more memory-intensive than an iterative approach. This stack frame contains the function's variables as well as its call history.

After the function is called, a stack frame is produced, and it is deleted when the function returns. Recursively calling itself results in the creation of a stack of stack frames, with each new stack frame being added on top of the previous one. This stack of stack frames can eat a lot of memory, especially if the recursion is having complex calculation or the function is invoked frequently.

Execution Speed

Recursion typically outperforms its iterative counterpart because it divides the problem into smaller subproblems, resulting in smaller chunks or tasks. Furthermore, as a bounty point, it makes the function simple to grasp and read.

However, it is critical to have a clearly defined base case that will stop the recursion and produce the result; otherwise, there is a risk of running into an infinite loop due to recursion, which can cause all sorts of problems, including bringing down the entire system's network. When using recursions, use caution at all times.

To summarize,

• Recursion is an effective technique for breaking down larger, more complex problems into smaller chunks.
• A recursive function is one that repeatedly calls itself.
• Always have a base case that stops the recursion and produces a result.
• Recursion can be used to create shorter, more readable code fragments.
• Recursion can be memory-intensive.
• Always use recursion with caution.

I hope you found this post interesting and learned something new today. Please add anything I missed in this article, and as always, Happy Learning!