Tail VS Non-Tail Recursion
When use rightly, recursion is a useful way of solving algorithm problems.
Understanding tail and non-tail recursion enables you to utilise the power of recursion.
This tutorial provides details on tail and non-tail recursion.
1.0 Introduction
When the invocation of a recursion is too deep, the available stack space will be exhausted, and adding a new frame will not be possible which will result to stack over flow error.
Consider the below example
1.1. Example of a recursive function
1.1.1. Problem → Return the sum of all numbers within a given integer
1.1.2. Solution
int sum(int n) {
if (n == 0) return 0;
return n + sum(n – 1);
}
When sum(3) is invoked, it will be executed as
sum(3)
3 + sum(2)
3 + (2 + sum(1))
3 + (2 + (1 + sum(0)))
3 + (2 + (1 + 0)))
3 + (2 + (1))
3 + (3)
= 6
1.1.3. Execution flow
The runtime of the above is: The number of times the above function was invoked x The runtime of each individual function call.
Each recursive call makes 2 additional recursive calls.
(i.) The worst-case depth of the recursion is the size of the given integer number
we intend to sum(n).
(ii.) The number of total calls is O(2N).
(iii.) Each individual function call does O(1) work. Therefore, the total
runtime is O(2N) * O(1) = O(2N).
The above will make the program prone to SO(StackOverflow) error when deeply recurs with values up to 50,000.
- Tail recursion
A function is said to be tail recursive if the recursive call is the last operation done by the function without keeping any record of the previous state.
2.1 How the tail recursion works
(i.) The recursive function is the last statement of the function.
(ii.) Nothing is left to do after coming back from the recursive call
2.2. Example of a tail recursive solution
Problem → Return the sum of all even numbers in a list
input = {1,3,2,4,5,9,12,10,8,7}
Output = {2, 4, 12, 10, 8} = 36
Solution
Step 1: Define the base case
Step 2: Invoke a generic solution
Step 3: Make recursive calls, and ensure it’s the last operation
Step 1: Define the base case
Provided the list is not empty, the base case is to have a single integer inside the list(i.e zero indexes)
public int sumOfEvenNums(List<Integer> x, int total, int index){
if (index == 0) {
return total + x.get(0);
}
}
Step 2: Provide a generic solution with the required condition
private int sum(int total, int currentValue){
return (total) + ( (currentValue % 0B10) == 0B0 ? currentValue : 0B0);
}
Step 3: Make recursive calls, and ensure it’s the last operation without keeping records of the previous operation. //Include flow diagrams
public static int sumOfEvenNums(List<Integer> x, int total, int index){
if (index == 0) {
return sum(total, x.get(0));
}
total = sum(total, x.get(index));
return sumOfEvenNums(x, total, index – 0B1);
}
3. Non-tail recursion
A function is a non-tail recursion if the recursive call is not the last operation performed.
3.1. Example of a non-tail recursion
Problem: Print the list of a given integer in increasing order
Input : n = 5
Output : 0, 1, 2, 3, 4, 5
3.2 Solution
Step 1: Define the base case
Step 2: Make a recursive call
Step 3: Print in increasing order
Step 1: Define the base case
public void printInAscendingOrder(int n){
if(n < 0) return;
}
Step 2: Make a recursive call
public void printInAscendingOrder(int n){
if(n < 0) return;
printInAscendingOrder(n-1);
}
Step 3: Print in increasing order
public void printInAscendingOrder(int n){
if(n < 0) return;
printInAscendingOrder(n-1);
out.println(n);
}
Example 2: Return the sum of all even numbers in a list
public static int sumOfEvenNumsNonTail(List<Integer> x, int total, int index){
if (index == 0) {
return sum(total, x.get(0));
}
return sum(total, x.get(index)) + sumOfEvenNums(x, total, index – 0B1);
}
4. Difference between the tail and non-tail recursion
| Tail | Non-Tail | |
| Memory | Depending on the problem, and implementation, few numbers of stack frames are required. | Many stack frames are invoked |
| Extensibility | Easy to extend into an iterative function | Difficult to extend |
| Readability | Easy to read | Difficult to read |
| Practical usage | Debugging a tail recursion is very difficult. | Not to be considered |
5. Tail recursion in a binary tree
Considering the below as the tree node
class Node{
int data;
Node leftNode;
Node rightNode;
}
5.1. Binary tree lookup
Problem 1 : Given a binary tree, return FOUND if a node with the target data is found in the tree, and NOT_FOUND if otherwise.
(i.) Base case(Null tree)
Not found, so return “NOT_FOUND”
if (node == NULL) {
return “NOT_FOUND”
}
(ii.) Check the current node, if found, return “FOUND”
if (target == node.data) return “FOUND”;
(iii) Otherwise recur down the correct subtree
If the target is less than the current node data, perform left traversal
if (target < node.data) return lookup(node.left, target); //Left traversal
If the target is greater than the current node data, perform right traversal
If (target > node.data) return lookup(node.right, target)
String lookup(Node node, int target) {
if (node == NULL) {
return “NOT_FOUND”
}
else {
if (target == node.data) return “FOUND”;
else {
if (target < node.data) return lookup(node.left, target); //Left traversal
else return lookup(node.right, target); //Right traversal
}
}
}
Time complexity : O (log n)
Space complexity : O(n)
//Flow diagram here
Amuda->Badmus 
Leave a comment