Algorithms: Tail Recursion (Part-1)
Exemplar Approach
Tail Recursion is another type of recursion that exists from various other forms. Last time we discussed about the Linear Recursion for Basic Problem. If you haven’t gone through it and want to get some overview of the process, consider this article:
Although, the Tail Recursion is a type of Linear Recursion only, but we are keeping it as a separate type to make distinction between the two.
What is Tail Recursion?
Tail Recursion happens when a regular Linear Recursion is made conditional in such a way that Recursive Case becomes a last resort to move further in recursive calls. This situation can appear when there a certain condition already satisfied and suffices the problem in question. Then in that case, it’s not needed to go for recursive case since it will only be an extra operation being performed.
Example
Suppose you are looking out for a string pattern in a larger string as an input. While a function is implemented to consider base case such as if input string is already empty or string is of length 1, whereas a recursive case is used to break down the problem further for in-depth search. The last case can be ignored if let’s say the string is already searched through first 2 or 3 steps, then the rest of the string doesn’t need to be searched and hence recursion occurs at the tail.
Tail Recursion is conditional in nature where if the condition is satisfied already, then the recursive case is not required to be called to go through rest of the input size.
It’s better to explain this in more depth by considering a problem. It’s a basic problem and already a lot of variation of the solutions exists. Here we are not going to consider all of them, but only the recursive relation method we learnt to apply. If you haven’t gone through it, feel free to have a look of the article:
Equal Strings
Problem: Given two input strings, check if they are equal or not?
Input: s1, s2
Function:
In the above recursive relation, we have defined 2 base condition, 1 short-circuit condition and 1 recursive case.
If you notice, we have put recursive relation at the very last which is called when all the conditions above it fails. For first two condition, we check if the length of two input strings are 0 then we say it’s True, otherwise we check if the length varies where the conclusion is False. 3rd condition is the Short Circuit condition which gets the first character of the input string to check if they are not equal. The moment this condition is true, we don’t even consider checking the further string characters and skip the recursive calls.
Finally, the thought process for the above function to work is to cut down the input size for both the input string by 1 character unit. In the recursive case we take the remaining size input string as input to check further characters in the two strings.
The code implementation for the above recursive relation can be given as:
#Python Function to check if two strings are equal or not
def equalStrings(s1, s2):
print('Input String S1: ',s1)
print('Input String S2: ',s2)
#BASE CASE 1
if len(s1) != len(s2):
return False
#BASE CASE 2
elif len(s1) == 0 and len(s2) == 0:
return True
#SHORT CIRCUIT CASE
elif s1[0] != s2[0]:
return False
#RECURSIVE CASE
else:
return equalStrings(s1[1:],s2[1:])
Conclusion
In this article, we introduced the Tail Recursion and it’s basic example to get an understanding how and where it can be applied mathematically. Once the mathematical base is set through Recursive Relation, we come to the code part to demonstrate the function and it’s conditions. In the upcoming article, we will discuss another core method given by Tony Hoare called Hoare’s Partition Scheme. Till then, happy coding!