"Tail Recursion" - The most unexplored topic.

Shashwat Gupta — Thu, 28 Jul 2022 07:20:00 +0000

Before we get into the core, let's revise some basics.

Recursion : It is a process in which a function repeatedly calls itself until a base condition is not reached or a desired result is not achieved.

Base Condition : It is a condition when the function stops making recursive calls and starts returning the result. And if this condition is not defined, the program might get into infinite loop which will cause Stack Overflow Error as the stack memory will get wasted.

Stack Overflow Error : To have a better understanding about what this is refer to my article on How Functions Work Internally so that you can learn about program stack, stack frame and everything else.
So, this error basically happens when the stack memory gets exhausted due to a large amount of incoming stack frames which can't be accommodated in the stack anymore.

So now let's get to the topic.

What is Tail Recursion?

A recursive function is tail recursive when a recursive call is the last thing executed by the function.
I know it didn't explained much about the topic. So let's see first what non-tail recursion is i.e. the traditional recursion that we all use mostly.

In traditional / non-tail recursion, the typical model is that you perform your recursive calls first, the you take the return value of the recursive calls and calculate the result. In this manner, you don't get the result of your calculation until you have returned from every recursive call. For ex:

main_function() {

    //Calculating the sum of N natural numbers

    int sum = nsum(5);
    display sum;
}

int nsum(int x) {

    if (x == 0) {    //base condition
        return 0;
    }
    else {
        return (x + nsum(x - 1));
}

For the above pseudocode, the control flow will be like :

It can be said that for the result to be computed, each and every recursive call has to finish it's operation first.

Now, in tail recursion, you perform your calculations first, and then you execute the recursive call passing the result of your current step to the next step. So, the return value of any given recursive step is same as the return value of the next recursive call. Let's visualize it through the pseudocode and it's control flow.

main_function() {

    //Calculating the sum of N natural numbers

    int sum = nsum(0, 5);
    display sum;
}

int nsum(int sum, int x) {

    if (x == 0) {    //base condition
        return sum;
    }
    else {
        return nsum(sum + x, x - 1);
}

The control flow goes like:

The consequence of tail recursion is that once the program is ready to perform the next recursive step, it doesn't need the current stack frame in the program stack anymore. This allows for some optimization as it can be seen from image (2) and (4) that the computation process of Tail Recursion takes much lesser time than the time taken by Non-Tail Recursion. With the tail recursive function, Stack Overflow Error might not be encountered.

That is all about Tail Recursion that you needed to know.

If you found the article interesting, please let me know in the comment section or if you have any doubts regarding it, please drop it in the same, I'll try to resolve it ASAP.

Thanks for reading ❤️

This is how functions work internally...

Shashwat Gupta — Thu, 28 Jul 2022 04:14:14 +0000

Hey folks, it’s mesmerizing how functions work internally, what happens in memory, how the calling mechanism works and much more….

So, before knowing what happens, we should know about :

a. Program Stack: A stack is a special area in memory which is used to store data temporarily. For functions, it holds all the function calls with bottom element as the main function because it’s the first function in a program that is executed and goes to the bottom of the stack.

It works on LIFO (first-in-last-out) principle i.e. what goes in first comes out last.

b. Stack Frame : It is a buffer memory which is an element of program stack and it has the data of the called function i.e. Return Address, Input Parameter, Local Variables, Register Savings.

c. Stack Pointer: It is the pointer which points to the stack frame in the program stack i.e. the most recent function called.

These three elements can be visualized as :

Now, let’s get to the interesting part :

Whenever a function is called, a new stack frame of the function is created with all the functions data in it.
The stack frame is pushed into the program stack.
The stack pointer that always points to the top of the stack points to the stack frame pushed recently.
When the function who’s stack frame is at the top finishes execution, it’s stack frame is popped (deleted) of the stack i.e. the functions data is deleted.
Now the control passes back to the function caller from where it was called or it can be said that the control goes to the stack frame which is now at the top after the frame that was above it got popped off.
The above process can be explained via the pseudo-code :

main_function() {

    func1();
}

func1() {

    func2();
}

func2() {

    // does some operation and returns
       back the results to func1()
}

As we know, main_function is always executes first in a program and according to the pseudocode above, (see in fig. a) it called func1() and as it was called, it’s stack frame was generated with all it’s data and was pushed (inserted) in the program stack with the stack pointer pointing to it as it is the frame pushed recently. When func1() started executing, (see in fig. b) it called func2() and similarly it’s stack frame also got pushed into the stack and the pointer points to it. When func2() finishes it’s execution, it’s stack frame consisting all it’s data got popped (deleted) off the stack (see in fig. c) and the stack pointer started pointing to func1() which is the function that called func2() and also it’s stack frame is at the top. And when each function’s execution will get over, their frames will be popped and the stack will be emptied.

Hope you understood….

Thanks for reading❤️

Forem: Shashwat Gupta

"Tail Recursion" - The most unexplored topic.

This is how functions work internally...