Demystifying Python Recursion

Demystifying Python Recursion

Most complex tasks in Python can be broken down into simpler subtasks. Recursion helps to achieve this, hence making the code clean and neat. This tutorial will introduce recursion, the benefits of recursion, and how to use it in Python programming.

What Is Recursion?

Recursion is a method of solving a problem with the solutions to smaller instances of the same problem. This approach can be applied to many types of challenges in programming.

The Benefits of Using Recursion

Some of the benefits of using recursion are:

• Recursion adds simplicity when writing code, hence making it easier to debug.
• Recursion reduces the amount of time taken by an algorithm to run as a function of the length of the input.
• Recursion is also preferred when solving very complex problems, especially problems on tree-based structures, because it performs better.

Introduction to the Python Recursive Function

Although recursion seems like a complicated procedure, it's not all that complicated. In layman's terms, assume you have two rectangles A and B. If you add them together, they form a rectangle C. This is in itself a recursive procedure. We have used smaller instances of a rectangle to define itself, and if we were to write a Python function, it would be as follows:

def rectangle(a,b):
    return a+b
    

Since a recursive function calls itself, there needs to be a rule or a breakpoint at which the process or loop would terminate. Such a condition is known as a base condition. A base condition is a requirement in every recursive program, otherwise the procedure would result in an infinite loop.

The second requirement is the recursive case when the function calls itself.

Let's look at an example:

In this example, you will write a factorial function that takes an integer (positive) as an input. The factorial of a number is obtained by multiplying the number by all positive integers below it. For example, factorial(3) = 3 x 2 x 1, factorial(2) = 2 x 1, and factorial(0) = 1.

The first thing to do is to define our base case, which will be factorial(0) = 1.

As you can see above, there is a relationship between each consecutive factorial scenario. You should notice that factorial(4) = 4 x factorial(3). Similarly, factorial(5) = 5 x factorial(4).

The second part will be writing a function that calls itself.

Now that we have simplified it, the resulting function will be:

def factorial(n):
    if(n == 0):
          #Define our base case?
                return 1  
        else:
                return n*factorial(n-1) 
                
print(factorial(5))

#result 

# 120

The solution if n==0 is:

def factorial(n):
    if(n == 0):
      #Define our base case?
                return 1  
        else:
                return n*factorial(n-1) 
                
print(factorial(0))

#result 

# 0

Now that you know how to write recursive functions, let's look at several case studies that will solidify your understanding of recursion.

Case Study 1: Fibonacci

In a Fibonacci sequence, each number is the sum of the two preceding numbers, such as: 1 + 1 = 2; 1 + 2 = 3; 2 + 3 = 5; 3 + 5 = 8. The Fibonacci sequence has been applied in many areas, and the most common is in predicting price action in the stock market by forex traders.

The Fibonacci sequence starts with 0 and 1. The first number in a Fibonacci sequence is 0, the second number is 1, and the third term in the sequence is 0 + 1 = 1. The fourth is 1 + 1 = 2 and so on.

In order to come up with a recursive function, you need to have two base cases, i.e. 0 and 1. You can then translate the adding pattern into the else case.

The resulting function will be:

def fibonacci(n):
    if(n == 1):
          #define Base case 1 
                return 0+1 
        elif(n == 2):
          #define Base case 1 
                return 1+2 
        else:
                return fibonacci(n) + fibonacci(n-1)
                
print(fibonacci(5))

#result

# 

Case Study 2: Reversing a String

In this example, you will write a function that takes a string as input and then returns the reverse of the string.

The first thing to do is to define our base case, which will check if the string is equal to 0 and, if so, will return the string itself.

The second step is to recursively call the reverse function to slice the part of the string excluding the first character and then concatenate the first character to the end of the sliced string.

The resulting function is as shown below:

def reverse(a):
  
    if len(a) == 0:
        return a
    else:
        return reverse(a[1:]) + a[0]

print(reverse("Python is a very easy language to learn"))

# result

#nrael ot egaugnal ysae yrev a si nohtyP

Case study 3: Sum of Elements

In this example, you will write a function that takes an array as input and then returns the sum of the elements in the list.

The first thing to do is to define our base case, which will check if the size of the list is zero, and return 0 if True.

The second step returns the element and a call to the function sum() minus one element of the list.

The solution is as shown below:

def sum_of_numbers(l):
   if len(l) == 1:
        return 0
   else:
        return l[0] + sum(l[1:])
        
a =[5,7,3,8,10]

print(sum(a))

# result
# 33

The solution for an empty list is as shown below:

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

b =[]
 
print(sum(b))

# result

# 0

Conclusion

This tutorial has covered what is necessary to use recursion to solve complex programs in Python. It's also important to note that recursion has its own limitations:

• Recursion takes a lot of stack space, hence making it a bit slow to maintain the program.
• Recursion functions require more space and time to execute.

Remember, don’t hesitate to see what we have available for sale and for study in the Envato Market, and please ask any questions and provide your valuable feedback using the feed below.