What is Recursion and TCO?

This article contains information about recursion in programming, its types and need of TCO (Tail Call Optimization).

What is Recursion?

Recursion is an approach to solve problems. In other words, recursion refers to a method which solves a problem by solving a smaller version of the problem and then using that result plus some other computation to formulate the answer to the original problem. Often times, in the process of solving the smaller version, the method will solve a yet smaller version of the problem, and so on, until it reaches a “base case” which is trivial to solve.

Recursion uses the data structure called “stack”. Internally, some space is created for each function (of function call) is known as “Activation Record” and that space is called “Stack Frame” in LIFO (Last In First Out) format. Whenever you call a function, including recursively, the return address and often the arguments are pushed onto the call stack. The stack is finite, so if the recursion is too deep you’ll eventually run out of stack space.

There are two types of Recursion ::

1. Head Recursion (Non-Tail)
2. Tail Recursion

Head Recursion

Head recursion means the recursive call is done first and then all required operations such as calculation, sending a mail or SMS, etc are performed. In other word, at first whole stack frame is created means, lot of activation records and then operation is performed. Given below is example of Factorial using head recursion,

There’s one problem in head recursion that, as all activation records consume some space and stack memory is finite. Hence, if someone pass larger data, more space will be consume so, after some time stack frame will become big and program will crash also, operation of each call is pending until last stack frame is reached. This problem can be solved by “Tail Recursion”.

Tail Recursion

Tail recursion means operation is done first and then recursive call happens. Given below is example of Factorial using tail recursion,

So, in this case, even if large data is passed on and program crashes, at least some operations are done. Therefore, in the above example, to find 5!, first execute 4!; to find 4!, first execute 3! and so on…

Note ::
1. Tail recursion is preferred over Head recursion.
2. Internally, Recursive Tree is created internally based on type of recursion.
3. Data structure called “Stack” is used for recursion and is finite.

What is TCO?

TCO (Tail Call Optimization) is the process of converting tail recursion into iteration. In other words, TCO (Tail Call Optimization) is the process by which a smart compiler can make a call to a function and take no additional stack space.

Why to use TCO?

One of the advantage of recursion is that, code is smaller and by using iteration (i.e. loops), constant time can be achieved. In-order to combine these, TCO is used. Main motive of TCO is to achieve optimized code. Below diagram shows how TCO works,

Note :: Developer should convert the recursion in Tail if, head recursion was created otherwise, TCO would not work.

Conclusion

Now you know, what is recursion, which type of recursion to be used and why TCO (tail call optimization) is a great concept.

Keep Learning
Thank You….