For software engineers, recursive thinking is a key factor in solving complex programming problems. It helps in breaking down larger problems into smaller subproblems, making them easier to visualize. Most FAANG and tier-1 tech companies ask candidates to come up with a recursive approach during technical interviews; the aim is to test their ability to solve problems. In this article, we focus on tail recursion:

• What is recursion?
• What is tail recursion?
• Why use tail recursion?
• Difference between tail and non-tail recursion
• Can a non-tail-recursive function be written as tail-recursive to optimize it?
• Tail recursion implementation: Example 1
• Tail recursion implementation: Example 2
• Advantages and disadvantages of tail recursion
• FAANG interview questions on tail recursion
• FAQs on tail recursion
  

What Is Recursion?

Recursion is a process in which a function calls itself, either directly or indirectly. The function involved is called a recursive function. The condition that terminates the further call of the function by defining the termination state is called the base condition.

Recursion is a very broad field and has many branches like:

• Linear Recursion
• Binary Recursion
• Tail Recursion
• Mutual Recursion
• Nested Recursion
  

This article, as you know, covers tail recursion. So let’s get right into it.

What Is Tail Recursion? 

In tail recursion, there is no other operation to perform after executing the recursive function itself; the function can directly return the result of the recursive call.

In simple words, in tail recursion, the recursive function is called last. So it is more efficient than non-tail recursion. Also, the compiler can easily optimize the tail-recursive function, as there isn’t any instruction left to be executed because the recursive call is the last statement. Hence, there is no need to save the stack frame of the function.

Here’s an example of tail recursion:

#include <bits/stdc++.h>
using namespace std;

// Find gcd of the number

int gcd(int a, int b)
{
        if(b == 0) {
                return a;
        }
        return gcd(b, a % b);          // Tail recursion
}

int main()
{
        int a = 10, b = 4;
        cout << gcd(a, b);
        return 0;
}

Why Use Tail Recursion?

Tail recursion functions are considered better than linear-, binary-, or mutual-recursive functions because a modern compiler can optimize them. Modern compilers implement a method called tail call elimination to optimize the tail recursion code.

Let’s look at our gcd function again:

int gcd(int a, int b)
{
        if(b == 0) {
                return a;
        }
        return gcd(b, a % b); // Tail recursion
}

We can easily convert this function with the help of the goto statement:

int gcd(int a, int b)
{

      start:
        if(b == 0) {
                return a;
        }

      int c = a % b;

      a = b;

      b = c;
        goto start;
}

Not only does tail recursion optimize time complexity by removing the overhead of the function call, but it can also optimize space complexity. Let’s see how.

Each function call requires its own memory space to get executed. For each function call, the activation record of the function or function’s stack frame gets stored on the top of the memory stack, which stores all the information related to the function, such as: 

• Local variables
• Return values
• Parameters of the function 
• Return address 
  

Let’s assume each function call requires constant or O(1) space, so for n function calls, it will require O(n) space. Tail recursion reduces the space complexity of the function from O(n) to O(1) with the help of the tail-call-elimination method. As no new function call occurs, no new stack frames are created, and the function is created in constant memory space. 

The function’s stack frame need not be preserved because:

• There is no instruction left to be executed after the recursive call of the function
• The function’s return value does not get used after the call

Hence, the function executes in constant memory space. This makes tail recursion faster and memory efficient.

Difference Between Tail and Non-tail Recursion

In tail recursion, there is no other operation to perform after executing the recursive function itself; the function can directly return the result of the recursive call.

In non-tail recursion, some operations need to be performed using the returned value of the recursive call.

Tail-recursive functions are considered better than non-tail-recursive functions — the compiler can easily optimize the tail-recursive function as there is nothing left to do in the current function after the recursive call. Hence, the function's stack frame need not be saved. 

Example: Tail recursion

#include <bits/stdc++.h>
using namespace std;

// Find gcd of the number

int gcd(int a, int b)
{
        if(b == 0) {
                return a;
        }
        return gcd(b, a % b); // Tail recursion
}

int main()
{
        int a = 10, b = 4;
        cout << gcd(a, b);
        return 0;
}

Example: Non-tail recursion

#include <bits/stdc++.h>
using namespace std;

// Find factorial of the number

int factorial(int n)
{
        if(n == 0) {
                return 1;
        }
        return n * factorial(n - 1);  // Non tail recursion
}

int main()
{
        int a = 10;
        cout << factorial(a);
        return 0;
}

Can a Non-tail Recursive Function Be Written as Tail-recursive to Optimize It?

Any recursive algorithm can be rewritten as an iterative algorithm, and every iterative algorithm can be written as a tail-recursive algorithm. Therefore, any recursive algorithm can be converted or rewritten as a tail-recursive algorithm by adding additional parameters to maintain the state of the recursive call.

Another way of converting is writing the iterative code for non-tail-recursive function and then deriving the tail-recursive algorithm from the iterative algorithm. However, for some recursive algorithms, this may compromise the algorithm’s time complexity and result in a more complex code.

But there are some exceptions; sometimes, converting a non-tail-recursive algorithm to a tail-recursive algorithm can get tricky because of the complexity of the recursion state. (The Tak function is a good example.)

Tail Recursion Implementation: Example 1

Problem: Write a recursive function to find the sum of n natural numbers where n >= 1

Let’s start with non-tail recursion:

#include <bits/stdc++.h>
using namespace std;

// Find sum of n natural number

int sum(int n)
{
        if(n == 1) {
                return n;
        }
        return n + sum(n - 1);
}

int main()
{
        int n = 4;
        cout << sum(n);
        return 0;
}

If we call the function for n = 4, then, since its value is greater than 1, it will go on a recursive call for n = 3. Similarly, for n = 3, it will go on a recursive call for n = 2. This continues until n = 1, as this satisfies the base condition. Here, when the recursive function returns the value, its value gets added with the value of n.

Since the return value is needed later in the program, the function's stack frame will remain in the memory to retrieve its return value when needed.

Here’s what it looks like:

sum(4) = 4 + sum(3)

             = 4 + (3 + sum(2))

             = 4 + (3 + (2 + sum(1)))

             = 4 + (3 + (2 + (1)) = 10

You can see that every function call needs to be completed before calculating the sum.

In this way, the space complexity of the function will be the number of frames remaining in the memory stack (equal to the total number of function calls). So the space complexity will be O(n).

Now, let’s solve this with tail recursion.

#include <bits/stdc++.h>
using namespace std;

// Find sum of n natural number

int sum(int n, int running_sum)
{
        if(n == 1) {
                return running_sum + 1;
        }
        return sum(n - 1, running_sum + n);
}

int main()
{
        int n = 4;
        cout << sum(n, 0);
        return 0;
}

Here, the recursive call is the last instruction to be executed. Not even a single operation depends on the return value of the function call.

Let’s call now call the sum function by passing n = 4 and running_sum = 0. So the sequence of function call will be:

sum(4, 0)
sum(3, 4)
sum(2, 7)
sum(1, 9)

Here, running_sum stores the total of each function call without waiting for the whole function call to get completed. Also, each function call is independent because we are not using the return value of any function call to find the result of the current function. Therefore, the total space complexity of the solution will be constant.

Tail Recursion Implementation: Example 2

Problem: Find nth fibonacci number using tail recursion

Fibonacci numbers are: 0, 1, 1, 2, 3, 5, 7, ...

#include <bits/stdc++.h>
using namespace std;

// Find nth fibonacci number

int fibonacci(int n, int first, int second)
{
/*

      For ith recursive call
        param first holds ith value in the fibonacci series
        Param second holds (i + 1)th value in the fibonacci series
        */

        if(n == 0) {
                return first;
        }
        if(n == 1) {
                return second;
        }
        return fibonacci(n - 1, second, second + first);
}

int main()
{
        int n = 10;
        cout << fibonacci(n, 0, 1);
        return 0;
}

In this program, instead of calling fibonacci number in a non-tail-recursive manner, we have used two variables (first and second) to maintain the function’s state. The first variable holds the ith Fibonacci number, and the second value holds the (i+1)th Fibonacci number for the ith recursive call. Here too, the function’s stack frame need not be preserved as its return value is used only in the current function call.

Advantages and Disadvantages of Trail Recursion

Advantages:

• Tail recursion optimizes the space complexity of the function by reducing the number of stack frames in the memory stack.
• As each function remains in the memory till it is executed, there is no stack overflow exception.
• Tail recursion also allows the compiler to perform special optimization, which cannot be done in non-tail recursion.
• Tail recursion often leads to a code that can easily be implemented using iterative techniques.

Disadvantages:

• Tail recursion, if implemented iteratively, is much more efficient because the compiler can theoretically perform various optimizations. But in practice, it is not often used because debugging the optimized code is tricky and requires the source code to remain in sync with the optimized code.
• For some cases, tail recursion solutions are not very efficient, and they also compromise the readability of the code.

FAANG Interview Questions on Trail Recursion

Following are a few examples of technical interview questions related to tail recursion that software engineers or developers can expect at FAANG and other tier-1 tech companies:

• Question 1: Write a space-optimized quicksort algorithm
• Question 2: Implement an algorithm to find the GCD of two numbers
• Question 3: Find the path in an array
• Question 4: Check if a number is a perfect square using binary search

FAQs on Trail Recursion

Question1: When should tail recursion be used?

Answer: Tail recursion is helpful in resolving the stack overflow error. Also, compiler optimization is possible in tail recursion, which makes the code more efficient. However, the downside is that it compromises the readability of code, and sometimes you need extra variables to maintain the state of the recursive function. So, you can use tail recursion when you think code efficiency is much more important than readability. Also, tail recursion code can easily be converted to iterative code, which is more efficient than tail recursion as there is no overhead involved in the function call and return.

Question 2: What are the problems that can easily be solved using tail recursion?

Answer: Many functions that are not obviously tail-recursive can be converted to tail-recursive form by adding some extra parameters. For example, the standard implementation of the recursive Fibonacci function is not tail-recursive. But, if we add two more parameters, it can easily be converted into a tail-recursive function.

Question 3: Is iterative implementation possible for every recursive algorithm?

Answer: Yes, every recursive algorithm can be rewritten as an iterative algorithm. To learn more about the differences between recursion and iteration and to understand when to use which, check out the article “Difference Between Recursion and Iteration.”

Ready to Nail Your Next Coding Interview?

Nailing tech interviews at FAANG and Tier-1 tech companies can be challenging even for seasoned software engineers. It requires a deep understanding of data structure and algorithms as well as systems design. 

If you’re looking for guidance and help to nail these questions and more, sign up for our free webinar. As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

Sign up now!

----------

Article contributed by Problem Setters Official