Python Recursion or Recursive Function in Python

Recursion occurs when a thing is defined in terms of itself. The most common application of Recursion is in Mathematics and Computer Science.

What is Recursive Function in Python?

In Python, we know that a function can call other functions. It is also possible for the function to call itself. These types of functions are known as Recursive Function.

It is very easy to write these functions but it is quite possible that the function which we have written calls itself and never terminates. Also, we have to be mindful of the amount of space and memory it uses. Albeit, when written correctly Recursive Functions are a very efficient and more elegant approach to programming.

Let’s see with some examples of how one can use Recursive Functions to their advantage.

Factorial

Many of you know, how to write a python code to find a Factorial for a given number. Let’s see the code for Factorial for those who are not familiar with it.

In the above code, we are basically multiplying the number in a for loop and adding that value to the variable every time.

Like this

f = 1
for i in range(1,n+1)
    f = f*i

Now, for the same Factorial problem, if we use recursion function, the python code will be as follows

In the recursive code, we created a function ‘factorial’ which takes one parameter ’n’. Now, inside that function, we are performing an operation ‘n*factorial(n-1)’, in which we are calling the same factorial function which takes the input as ‘n-1’. This process of function calling keeps on repeating until the ’n’ value reaches ‘0’.

Every Recursive Function must follow 3 main conditions.

1. Base Case or Base Condition
2. Recursive Call
3. Action

1. Base Condition

Every Recursive Function must have a Base Condition, which helps the function to stop the recursion. Without a base condition, the function calls itself infinitely.

In the above Factorial program, the recursion ends when the ’n’ value reaches ‘0’. That is our Base Condition

if n == 0:
   return 1

2. Recursive Call

In the factorial program, the function ‘factorial’ recursively calls itself by decreasing the ‘n’ value by 1.

Each time the number multiplies with the factorial of the number below it until it reaches ‘0’.

else:
    return(n*factorial(n-1))

3. Action

Action in a Recursive Function is basically, what is the operation you are performing in the program to get the desired output.

n*factorial(n-1)

In the code, we are multiplying the current number with the factorial of the previous number. The action part here is multiplying with the number ‘n’.

So, it is imperative to follow these 3 rules when we are writing a Recursive Function.

Advantages of Recursive Functions

1. If we wants to make our code look elegant and neat, recursive functions make sure of that.
2. A complex operation can be divided into similar sub-problems using recursion.
3. Recursive Functions are more useful in ‘Sequence Generation’ problems.

Disadvantages of Recursive Functions

1. It is hard to debug recursive functions.
2. Sometimes the logic behind recursive function is little difficult to follow.
3. They takes up a lot of space and time while executing.

Before we wind up, let’s take a look at another example for better understanding.

Fibonacci

We all know what is a Fibonacci series looks like, for those of you who are not familiar with it please click here.

The Python Code for Fibonacci series without using the recursive function is as follows

Now, let’s see how we can modify the same code using recursive function.

Let’s check the previously discussed 3 rules in the above program

1. Base Condition

The base condition here is, if the number is less than or equal to 0, we get out of the function.

if n <= 1:
   return n

2. Recursive Call

In the else part of the function we are calling the fibaonacci function again.

else:
    return(fibonacci(n-1) + fibonacci(n-2))

3. Action

The action part here is, adding the previous two elements.

fibonacci(n-1) + fibonacci(n-2)

Conclusion

Like I already mentioned, recursive functions make our program more elegant and it’s also easy to write once you get the hang of it, but they have their share of drawbacks too.

So, use them wisely and make sure you define the base condition.

Thank you for reading and Happy Coding!

If you are interested in more of my writing check out my previous articles on Python

1. Python: Problems for Basics Reference — Swapping, Factorial, Reverse Digits, Pattern Print
2. Python Programs to check for Armstrong Number (n digit) and Fenced Matrix

References

• Python Function Recursion: https://www.w3schools.com/python/gloss_python_function_recursion.asp
• Python Recursion: https://www.programiz.com/python-programming/recursion
• Thinking Recursively in Python: https://realpython.com/python-thinking-recursively/
• Recursive Functions: https://www.python-course.eu/recursive_functions.php
• Python Recursion: https://beginnersbook.com/2018/02/python-recursion/
• Python — Recursion: https://www.tutorialspoint.com/python_data_structure/python_recursion.htm
• Recursion in Python: https://realpython.com/binary-search-python/
• Recursion: https://en.wikipedia.org/wiki/Recursion
• Fibonacci number: https://en.wikipedia.org/wiki/Fibonacci_number