Understanding the problem

Now that we know the basics of memory layout, stack frames, and how nested function calls work, we will dive deeper into recursion in this module. Recursion is fundamental to many optimization problems and high-level concepts like memoization and dynamic programming. Understanding recursion is the first step to understanding dynamic programming and divide-and-conquer algorithms.

Simply put, recursion can be defined as solving a problem by solving a smaller version of the same problem or defining a problem in terms of itself. It is not always obvious if a problem can be solved using recursion at first sight. Let's take a real-world example to understand recursion better.