These are the special type of recursive functions, where the last statement executed inside the function is the call to the function itself.
Advantages of implementing Tail Recursive function
- In this concept, the compiler doesn’t need to save the stack frame of the function after the tail-recursive call is executed.
- It uses less memory as compared to non-tail recursive function.
- It is faster as the compiler can do special optimization on tail-recursive function calls.
Note: In Python, the interpreter doesn’t perform any special optimization even if the function is a tail-recursive function.
Example of Python Tail Recursive function Structure
In this example, we are just trying to emulate the structure of a tail-recursive function in Python. But in reality, this structure is the same as any other recursive function in Python.
Python3
def count(n): if n < 0: return print("Counting", n) count(n-1)count(3) |
Counting 3 Counting 2 Counting 1 Counting 0
Time Complexity: O(n)
Auxiliary Space: O(n)
But, the above example, similar to any recursive function in Python, also has the disadvantage of limited recursive calls. To overcome this, we can convert the recursive structure of the function into an iterative structure using Python decorators.
Difference between Tail Recursive function and Recursion in Python
Tail recursive function
Python3
def count(n): if n < 0: return print("Counting", n) count(n - 1) count(3) |
Counting 3 Counting 2 Counting 1 Counting 0
Time Complexity: O(n)
Auxiliary Space: O(n)
Simple Recursive Function
Python3
def count(n): if n < 0: return 0 print("Counting", n) n -= count(n-1) return ncount(3) |
Counting 3 Counting 2 Counting 1 Counting 0
Time Complexity: O(n)
Auxiliary Space: O(n)
Converting Tail Recursive function into Iterative function using Python decorator.
Python3
# class to define our own exceptionclass Recurse(Exception): def __init__(self, *args: object) -> None: super(Recurse, self).__init__() self.args = args# function to simulate the # tail-recursive calldef recurse_sim(*args): raise Recurse(*args)# decorator function to convert # recursive -> iterativedef iterative_recursion(fn): def wrapper(*args): while 1: try: return fn(*args) except Recurse as exc: args = exc.args return wrapper# tail recursive function # implementation@iterative_recursiondef count_pseudo_recursive(n): if n < 0: return print("Counting", n) return recurse_sim(n - 1)# function call to start the# tail recursioncount_pseudo_recursive(3) |
Counting 3 Counting 2 Counting 1 Counting 0
The above Python code gives output exactly the same as the normal Python code, with the tail-recursive structure. The only difference is, that this function can run for greater numbers without raising RecursionError in Python.
Explanation:
- Recurse exception class: This class is used to break the program flow, and also store the arguments function arguments to be used iteratively in the next call.
- recurse_sim function: This function is used to simulate the tail-recursive process and also raise the exception so that we can use arguments iteratively.
- iterative_recursion and wrapper function: This function is used as a decorator to convert the recursive process into an iterative process. The wrapper function handles the raised Recurse exception and uses the arguments from the exception class to call the same function with the collected arguments.
- count_pseudo_recursive function: This function is a pseudo-recursive function, that calls the recurse_sim function instead of itself to start the iterative process in a recursive way.
Advantages of this process:
- This process can run infinitely, unlike normal recursion, which will raise RecursionError if it exceeds max recursion depth.
- It uses less memory than recursion, as no need for storing stack frames.
- Can be used as an alternative to the usual Python recursion, also keeping memory usage low. This can be used in places where we need more recursion depth than defined by default in Python.
Disadvantages of this process:
- We have to write more amount of code to do this optimization.
- Using a self-defined (Recurse class) exception to raise an Error is a hacky way of doing the process since there’s no actual optimization from the interpreter side.
- The current way of defining the process makes the code look more complex and destroys the readability of the code.
You’ll access excellent video content by our CEO, Sandeep Jain, tackle common interview questions, and engage in real-time coding contests covering various DSA topics. We’re here to prepare you thoroughly for online assessments and interviews.
Ready to dive in? Explore our free demo content and join our DSA course, trusted by over 100,000neveropen! Whether it’s DSA in C++, Java, Python, or JavaScript we’ve got you covered. Let’s embark on this exciting journey together!
