Ermin Hodžić

The goal of this article is to provide a comprehensive review of recursion -- what the main idea is, why it works, how to use it to solve problems and integrate it into the reader's toolset. Some advanced algorithmic techniques and data structures heavily rely on recursive code, or require "recursive thinking" in order to solve problems. Examples of such techniques are divide & conquer and dynamic programming, foundation for both of them being recursion, as well as various graph-traversal-based algorithms such as computing strongly-connected components, discovering articulation points, and topologically sorting directed acyclic graphs. Additionally, data structures such as binary search trees, interval trees and segment trees are naturally recursive structures. Without a good understanding of recursion, one might find it much more difficult to understand and learn the above-mentioned topics.

This manuscript attempts to engage readers of various levels of expertise in the topic of recursion. Effort has been made to write it so that even complete beginners to recursion (but not to programming) should be able to understand a good part of the presented material and get a good grasp at what recursion is and how it works. However, there is no lack of explanation of advanced concepts everywhere in the manuscript for the more experienced reader, and there is some overlap with other topics in computer science that recursion naturally touches upon. Going in-depth on such topics is out of the scope of this manuscript, and where such topics are introduced, it is to help with the explanation of some aspect of recursion, or to demonstrate a possible use case.

Please refer to the PDF LaTeX document for the description.