Recursion

What is Recursion?

Recursion is a method of program design where you break apart a problem into smaller repeatable subtasks. The program will complete each subtask later combined to achieve a solution.

The primary feature that defines recursion is that a recursive function calls itself, either directly or indirectly during execution. The call usually comes at the end of another operation using the passed data, a practice called tail recursion. This results in a looping structure that repeats the operation until an exit condition is met.

Each pass through this loop brings the program closer to its desired state or solution, which is known as the base case. Once this base case is reached, the method will no longer loop back into its recursive step. Instead, the program will end.

Fundamental Concepts of Recursion

Base Case

The base case (or base condition) is the state where the program’s solution has been reached. An achievable base case is essential to avoid an infinite loop. Recursive methods are built with two paths: the method first checks if the base state has been reached, if yes, the method ends and returns the current data, if not the method instead goes the other path and executes the recursive case, altering the input and calling the method again.

To help contextualize this, consider a hypothetical example.

Imagine a search program’s base case is when a searched value is found, or valuesearched = cellvalue. If the values don’t match, the currently selected cell isn’t the solution.

The method then executes the recursive step, selecting another item in the data set and calls the method again using this new cell as input.

If we did not have the base case, the program would simply repeat the recursive step and therefore scroll the data set infinitely.

Call Stack

The call stack is an integrated, hidden data structure within all modern programing languages. By storing active subroutines in a stack structure, the program is able to execute subroutines in the order they were received.

Each recursive call in a program causes a nesting effect in the call stack, adding more subroutines that must be finished before the stack is empty.

Broadly speaking, the larger the call stack, the more memory and time that is needed for the program to run.

Tail Recursion

Tail recursion is when the recursive call for the next cycle is the final statement in a method.

Tail end recursion is considered good practice whenever possible because it is easier to follow from a reader’s perspective and it can be optimized by modern compilers.

Compilers can recognize that a tail ended method has completed all the operations within that call. Since all the work is complete, the program doesn’t need to store the instance of that call, known as the call frame.

Modern compilers automatically recognize this and therefore perform tail call elimination, which eliminates all completed methods from the call stack.

Compiler’s use tail call elimination to simplify program execution and free up memory. The program stores the currently executed call frame.

Though right now we’ve only mentioned direct recursive calls, there are actually three ways to implement a recursive call — Direct, Indirect, and Anonymous.

Benefits and Limitations of Recursion

These are all helpful ways to discuss and understand this concept, but why should you learn about recursive programming? The secret lies in ease of use!

For problems featuring repetitive, smaller problems, such as most search functions, a recursive solution can be the most efficient as it is intuitive and requires less code to implement.

Also, recursive solutions are easy to scale to any size because they will always run until the base state is reached.

While easy to scale, the shortcomings of recursive solutions become more pronounced with scale. Without tail recursion and tail end elimination, recursive solutions will use more memory for each method stored on the call stack — the greater the scale, the more methods on the call stack. More memory used will slow down the process.

Another main downside is difficult to read and troubleshoot at greater complexity levels. especially if using indirect recursion.

Finally, recursive solutions are sensitive to errors. A recursive solution can easily have either an unreachable base case or with a recursive step which does not correctly progress toward the base case. Both of these errors cause a stack overflow error, meaning that the recursive call resulted in an infinite loop and was therefore terminated.