Recursive Functions in Python

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?
• Why is it useful? Where can it be used?
• Different types of functions?
• How to define a function? What are the involved parameters and arguments?
• How to call a function?
• Recursive function
• Types of Recursive functions
• Iteration Vs Recursion
• Advantages and disadvantages of Recursive function

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.

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?

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:

maximum(100023, 1000248, 10012)

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:

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:

def factorial(n):
 if n < 0 or n == 1:
 # The function terminates here
 return 1
 else:
 value = n*factorial(n-1)
 return value

# Returns the factorial of 5
factorial(5)

120

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

# Call the function 'odd'
odd(1)

2

# Call the function 'odd'
even(2)

1

# ----- 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)

# Call the function 'recursive_factorial'
recursive_factorial(3)

6

# ----- 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

# Call the function 'iterative_factorial'
iterative_factorial(3)

6