madaramebak

Tail Call Optimization and recursive functions

Recursion and how it's often used suboptimally:

Recursion. You're probably familiar with this accursed technique due to the hours you spent doing problems studying for your intro to CS class in college. For those of you unfamiliar, Recursion is basically a technique where a function calls itself to solve a problem by breaking it down into smaller instances of itself. Now besides being frustrating to apply sometimes it has another major problem: Every single time a function is called it has creates a stack frame in memory, so if a recursive function has a very large input it would have to store a lot of stack frames which results in linear space complexity.

fib.png

Image src

How to optimize it's memory usage:

In comes TCO, otherwise known as Tail call optimization. Essentially TCO is a compiler/interpreter technique that transforms any function call in tail position into efficient iterations rather than creating new stack frames. (Although it should be noted that only certain languages support TCO, often just functional programming languages).

Screenshot 2025-04-20 092731.png

Image src

Why is this useful for techniques like recursion? Since TCO optimizes recursion into using the same stack frame for every single call, it results in it using the same space complexity as an iterative function which is constant not linear (which is a dramatic difference in memory usage). Another important use case is that TCO prevents Stack overflow errors that would normally occur in infinite recursion.