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
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.
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.
Primarily, there are three types of functions in Python:
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
min()to find the respective maximum and minimum values for any set of data.
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.
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.
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.
Step-1- Using the keyword
deffollowed by the function name is to define a function.
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_seriesinstead of let’s say
fib_ser. An opening parenthesis is followed by the function name where you pass the required parameters. For example,
Step-3 There are four different types of arguments:
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
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.
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.
Variable number: When you are not sure about the numbers of arguments that will be passed to a function. The syntax is as follows:
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 :
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
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)
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 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:
- Base case or termination case
- 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.
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)
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.
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:
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)
# Call the function 'odd' even(2)Out:
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.
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:
# ----- 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)
# ----- 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)
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.
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.