Recursive Functions in Python

9 min read

By Prachi Joshi

Ken Thompson had once said -“One of my most productive days was throwing away 1000 lines of code.”.

And I believe, this is partially achievable with the help of Functions!

Have you come across an incomprehensible, trivial length of the program, that possibly has a lot of repetitive line of codes just adding to the enigma? Redundancy is never appreciated because it disobeys the very basic principles of coding. The ability to write a clean, easy to understand code with high readability, goes to show how good a programmer you are. In this blog, we will cover how to create, define and call a recursive function and where such functions can be used.

This blog on ‘Recursive functions’ will walk you through a helpful framework to understand the various properties of functions and recursive functions in particular. Using various examples, we will help you learn how to create, define and call a recursive function.

In this blog, we will cover the following topics:

What is a function?

Functions are one of the building blocks of programming. One of the easiest ways to conquer an incomprehensible and huge code is to understand the importance and usability of functions. Functions have been used for a very long time in mathematics. F(x)=x^2 is a function, for which the output will vary depending on the value of x.

Functions are built on a certain set of instructions to produce the desired outcomes. The main idea behind using functions is to avoid redundancy by putting together the repeated code and make a function out of that. Now, instead of writing the code again, you can just call the function.

Why is it useful? Where can it be used?

Without a doubt, functions play a crucial role in programming. Let me list down a few pointers that make it easier to understand the use case. It goes without saying that incorporating functions in the program improves its readability. Functions give a logical structure to the program. Reusability is another advantage, wherein once defined, it can be called many times within the same program and other programs as well. It also improves the length of the code, makes testing and debugging much easier, and also functions are portable, which means that they can be stored in a library or .py file can be used in different programs as well. These are a few of the many advantages of functions.

Different types of functions?

Primarily, there are three types of functions in Python:

  1. Built-in functions are some of the ready-to-use functions that Python provides and are inbuilt in any Python environment. These are usually common to Python packages and libraries. For example, Python allows you to use max() and min() to find the respective maximum and minimum values for any set of data.

  2. User-defined functions are the reusable code blocks, customized functions that we have been talking about so far. These functions help us to achieve a particular task. You will learn how to create these user-defined functions in detail in this blog.

  3. Anonymous functions, also called as lambda functions. Unlike the user-defined funtions, lambda function is an in-line function, which allows constructing in blocks. We won’t be discussing these functions in further detail but these functions don’t have any named identifier like the other two. You can read about this function in this blog.

How to define a function?

Suffice to say, that, so far, you must have understood the importance of user-defined functions. Now, let’s learn how to define and create a function. We have mentioned a few ways below.

  1. Step-1- Using the keyword def followed by the function name is to define a function.

  2. Step-2 - Set an easy to understand function name. This function name must be self-explanatory for anyone having a glance at your code. Let's say you have to create a function to calculate the Fibonacci series. You can set the name as fibonnaci_series instead of let’s say fib or fib_ser. An opening parenthesis is followed by the function name where you pass the required parameters. For example, def fibonnaci_series():

  3. Step-3 There are four different types of arguments:

    1. Default: It is the argument that assumes a default value if no other value is assigned while calling a function but it is already assigned while defining a function. The default value is assigned by using a ‘=’ operator. For example, def class( student_name='John'):. Now, if you call the function class(), it will print 'John'.

    2. Required: The arguments are expected to be passed in the correct positional order, otherwise, the output shows an error. For example, you define a function def class( student_name): but you call class(). Then, this will definitely show an error because the function expects you to pass that one argument and you have passed none.

    3. Keyword: These are the keywords that you pass in the function for easy identification. Even if you call a function with keywords not in the same order as you passed while defining a function, it won’t make much difference. For example: Let’s say you define a function class with two arguments teacher_name and student_name, these two are the keywords. def class(teacher_name, student_name): If each time you call the function and specify the keywords, then the order won’t matter. For example, class(student_name= ‘John’, teacher_name= ‘Ms. Jasmine’) It will not affect the output or program in any way.

    4. Variable number: When you are not sure about the numbers of arguments that will be passed to a function. The syntax is as follows: def variable_length(*varargs):

A final parenthesis to close the argument is followed by the argument. And, finally you end the declaration using a colon :. Within this function, you write the program and finally, you can end it with return, print or atleast have pass statement within it.

Alright, let’s say just like the already existing in-built function ‘max’, you decide to create your own max function to find out the highest number amongst three numbers.

In [0]:
def maximum(a, b, c):
 if (a >= b) and (a >= c):
 largest = a
 elif (b >= a) and (b >= c):
 largest = b
 else:
 largest = c
 return largest

How to call a function?

Once defined, it doesn’t have to be defined again. All you have to do is to call the function. When you call a function you don't need to know what is happening inside but only what it is capable of doing. If we see the function defined in the above cell, the 'maximum' function is capable of finding the maximum of three numbers. You can manipulate the function to find maximum of more numbers as well but this is just for your reference.

Suppose you wish to find the highest of these three numbers: 100023, 1000248, 1000362. All you have to do is pass these numbers as the arguments within the function.

Like shown here:

In [0]:
maximum(100023, 1000248, 10012)
Out[0]:
1000248

TADAA!! 1000362 is the highest of the three. You will get the result within seconds. In fact, the way you were able to create your own maximum function, Python has an extensive library consisting of similar ready-to-use functions. User-defined functions can also be built for complicated programs.

Now that you have a slight idea of what really goes on within the whole process of defining, creating and calling a function. Right? Let's understand recursive functions.

Recursive Functions

Recursive functions are those functions that call itself within a function. But first, let me ask, what’s recursion? Recursion is the procedure wherein a procedure goes through when one of the steps of the procedure involves invoking the procedure itself. Here, the procedure gets repeated in the procedure itself. A procedure that goes through recursion is said to be 'recursive.

Simply said, recursive functions are the functions that call itself. A recursive function always has to say when to stop repeating itself.

A recursive function is divided into two cases:

  1. Base case or termination case
  2. And, recursive case

For any recursive function, it becomes crucial to distinguish and identify between the base case and recursive case. The base case plays a vital role in a recursive function. Why, you ask? The base case defines termination. Like any other function that stops after reaching and getting their output, the recursive function doesn’t terminate. It becomes an endless cycle that needs to put an end to. Remember that base case is important; otherwise, you won’t get the desired output. Missing base case results in unexpected behaviour. A base case is when the function stops calling itself but in the recursive case, function calls itself again.

Alright, so this is the basic structure of a recursive function:

In [0]:
def factorial(n):
 # Base case
 if n < 0 or n == 1:
 # The function terminates here
 return 1
 else:
 # Recursive case
 value = n*factorial(n-1)
 return value

A factorial is multiplication of all integers smaller than or equal to n. The factorial of n is denoted as n!.

Note: The base case as you can see is a conditional statement that is factorial for both 0 or 1 is 1. Once the base case is identified, your function will not show any error whatsoever. Factorial of 1 or 0 terminates the recursion, avoiding an infinite loop.

Types of Recursive functions

Primarily, there are two types of recursive functions. Functions that call itself or two functions that call each other mutually. The functions that call itself are direct recursive and when two functions call each other mutually, then those functions are called indirect recursive functions.

Direct recursive functions

These functions are the same recursive functions that you have been learning till now. When a function calls the same function again, you call it a direct function. Factorial is an example of direct recursive as shown below:

In [0]:
def factorial(n):
 if n < 0 or n == 1:
 # The function terminates here
 return 1
 else:
 value = n*factorial(n-1)
 return value
In [0]:
# Returns the factorial of 5
factorial(5)
Out[0]:
120

Indirect recursive functions

In Indirect recursive functions, two functions mutually call each other wherein both the functions must have a base case. Let's understand using a flowchart.

title

Here, function1 calls function2 which in turn calls function2 which calls the first function. This can be explained using an example. Suppose, you have a list of 10 numbers. For every odd number in the list, you add 1 to the number and for every even number in the list, you subtract 1. If the number is 1, output should be 2 and similarly, if the number is 2, output must be 1. You can employ indirect recursive functions to solve such problems like shown here:

In [0]:
def odd(n):
 if n <= 10:
 return n+1
 n = n+1
 even(n)
 return
def even(n):
 if n <= 10:
 return n-1
 n = n+1
 odd(n)
 return
In [0]:
# Call the function 'odd'
odd(1)
Out[0]:
2
In [0]:
# Call the function 'odd'
even(2)
Out[0]:
1

This is just for illustration purpose. These functions are mostly considered the least practical. Use case of indirect recursive is not very diverse and such problems can be even solved using single line of code as well.

Iteration Vs Recursion

The concept of recursion and iteration is pretty much the same. Both execute a set of instructions repeatedly to achieve the desired output, but only the methodology differs. Simply said, recursive functions call itself during its execution, enabling the function to repeat itself several times. Whereas iterative functions follow a set of instructions, these instructions are repeated in a sequence a specified number of times or until a condition is met. Recursive functions are commonly used in computer science because they allow programmers to write efficient programs using a minimal amount of code. The downside is that they can cause infinite loops and other unexpected results if not written properly. This is one of the core difference between iterative and recursive functions. Iterative functions are the best bet when time complexity is an issue because the number of iterations is defined or can be easily defined, which is not the case for recursive functions. The recursive function has a relatively smaller and shorter code than the iterative function.

To understand better, go through these two blocks of code:

In [0]:
# ----- Recursion -----
# Method to find factorial of given number using a recursion function
def recursive_factorial(n):
 if (n == 0):
 return 1
 return n * recursive_factorial(n - 1)
In [0]:
# Call the function 'recursive_factorial'
recursive_factorial(3)
Out[0]:
6
In [0]:
# ----- Iteration -----
# Method to find the factorial of a given number using an iteration function
def iterative_factorial(n):
 product = 1
 for i in range(1, n + 1):
 product = product * i
 return product
In [0]:
# Call the function 'iterative_factorial'
iterative_factorial(3)
Out[0]:
6

Advantages and disadvantages of Recursive functions:

The advantages of recursive functions are that it improves the readability of the code, adds clarity, makes it look organized, and reduces time complexity. The Tower of Hanoi problem is better solved using recursion function than any other function.

When it comes to the disadvantages, recursive functions are slower than iterative functions. It causes stack overflow when recursion gets deeply involved. It gets a little difficult to debug with every step in recursion.

Conclusion

Thus, you have learned the importance and usability of functions, different types of functions, how to define and call a function, what are recursive functions, types of recursive functions and, the difference between recursive and iterative functions. I'd like to suggest that you should explore more and implement this in your coding journey. Good Luck!

If you want to learn various aspects of Algorithmic trading then check out the Executive Programme in Algorithmic Trading (EPAT®). The course covers training modules like Statistics & Econometrics, Financial Computing & Technology, and Algorithmic & Quantitative Trading. EPAT equips you with the required skill sets to build a promising career in algorithmic trading. Enroll now!

Disclaimer: All data and information provided in this article are for informational purposes only. QuantInsti® makes no representations as to accuracy, completeness, currentness, suitability, or validity of any information in this article and will not be liable for any errors, omissions, or delays in this information or any losses, injuries, or damages arising from its display or use. All information is provided on an as-is basis.