Tag: recursion

recursion in python

Recursion is a widely-discussed concept not just in programming, but also in day-to-day language. An example from the English language that beautifully captures recursion is “To understand recursion, you must first understand recursion”. Similarly, the saying “A human is someone whose mother is human” offers another simple explanation.

Now, pivoting to programming, you may ask: How is this relevant?

In the realm of problem-solving, often there’s a need to break down a large, intricate problem into smaller, manageable parts. While you might be accustomed to using loops or iterations for such purposes, sometimes, recursion provides a more elegant and intuitive solution.

So, what exactly is recursion in Python? A function is termed as recursive when it makes a call to itself, but it’s imperative that this function has a stopping point or a termination condition. This ensures that the function doesn’t end up calling itself endlessly.

Recursion in Practice

List-Based Recursion Example

Consider a simple task of summing all numbers in a given list. A non-recursive approach to achieve this would be:

#!/usr/bin/env python

def sum(list):
    sum = 0

    # Iteratively add each number in the list.
    for i in range(0, len(list)):
        sum = sum + list[i]
    
    # Return the computed sum.
    return sum

print(sum([5,7,3,8,10]))

The above approach is straightforward: we iterate through each element and accumulate the sum. But how can we approach this using recursion?

#!/usr/bin/env python

def sum(list):
    if len(list) == 1:
        return list[0]
    else:
        return list[0] + sum(list[1:])

print(sum([5,7,3,8,10]))

Here, if the list contains just one element, that element is returned (acting as the termination condition). Otherwise, the function adds the first element to the sum of the rest of the list (achieved through a recursive call).

Factorial Using Recursion

Factorials are often calculated using recursion in programming. The mathematical definition states: n! = n * (n-1)!, given n > 1 and f(1) = 1. For instance, 3! = 3 x 2 x 1 = 6. Here’s how you can compute factorials recursively in Python:

#!/usr/bin/env python

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(3))

In the above code, as long as the input is greater than 1, the function keeps calling itself, thus calculating the factorial in a recursive manner.

Constraints of Using Recursion

It’s essential to understand the limitations of recursion. Each time a function calls itself, it uses some memory to store return values. Because of this, a recursive function can sometimes use a lot more memory compared to its iterative counterpart. In Python, recursion is limited to a depth of 1000 calls. If you try to surpass this, as demonstrated below:

#!/usr/bin/env python

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(3000))

You’ll be met with the error:

RuntimeError: maximum recursion depth exceeded

Some languages might crash your program under such conditions. While you can tweak the maximum recursion depth in Python, as shown:

#!/usr/bin/env python
import sys

sys.setrecursionlimit(5000)

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(3000))

Remember that this isn’t a foolproof solution. There will always be a threshold, and for problems like calculating large factorials, a recursive function might not be the most efficient choice. However, for tasks like directory traversal, recursion can be quite handy.