Recursion is the act of defining something in terms of itself. Think of two mirrors in front of each other. They will infinitely reflect each other. You can also illustrate it statements such as: "To understand recursion, one first need to understand recursion". At a basic level, recursion is a paradox because it results in an infinite loop. If you want to know the definition of a "tool", and your dictionary gives you "A tool is a tool we can use to accomplish a task", you will go back and forth between the entry and its definition, because understanding the definition involves you looking at the definition of the word in terms of which the word has been defined. On its own, recursion isn't very helpful. Combined with a **base case**, however, it becomes a powerful pattern that allow us to solve a surprising number of problems. A base case is a condition that tells the recursive function when to exit the infinite loop we were discussing earlier. Imagine you're programming a video game, where two mirrors can stand in front of each other. The mirrors are supposed to reflect whatever is in front of them, but you also don't want them to reflect each other infinitely. Infinitely many operations isn't something that fits into your computer's memory, and no player will wait an infinite amount of time before each and every frame of the game. To fix that, you use a base case. You could tell the computer to compute the reflection in each mirror until a reflection gets smaller than a pixel, or you could limit the numbers of reflection to a fixed number. Alternatively, of course, you could avoid putting mirrors in front of each other in the game. Now that we have recursion and a base case, let's see how they work together and how we can create loops from them. A classical example is factorial. ```cpp #include <iostream> int factorial(int n) { if (n <= 1) // base case { return 1; } return n * factorial(n - 1); // recursive step } int main() { int result = factorial(9); // 362880 std::cout << "The factorial of 9 is: " << result << std::endl; } ``` The **call stack** is what makes recursion possible in software engineering. Every time a function is called, it's pushed onto the stack, until the base case is reached. Once that happens, the functions start to return and the results are unwound from the stack, allowing the values to be computed and returned up the chain. The first thing that gets evaluated at the multiplication step is the recursive call. Before the function we're in can return, we must wait for that recursive step to return, which in turn must also wait for its recursive call to return... until there are no more calls to push onto the stack. This mechanism prevents infinite loops, because the stack has a limited size, so too many recursive calls creates a stack overflow and causes your program to crash. This is what you get if you forget to throw in a base case. You can think of the call stack as a pile of books inside a cabinet. You add books on books on books until your cabinet is filled. You can only grab the book that is on top if you want to grab subsequent books, following a Last-In, First-Out (LIFO) principle. The stack works the same way. Each recursive function call is like a new book placed on top. We could extend the logic from our example to create a function `loop` that accepts a number `i` representing the total number of needed repetitions and a `fn` callback function that needs to be called upon each iteration. The factorial example, while more intuitive because it is simple, doesn't provide any real benefits compared to an iterative version of the program. Many applications, however, make much more sense when they're defined recursively. Parsers, for instance, are often defined recursively, because it's much easier to think about the program that way. Otherwise you'd need loops within loops within loops... Fractals like the [[Overview of the Mandelbrot Set|Mandelbrot Set]] or the Sierpinski triangle are often generated using recursive implementations because of their self-similar nature. Hopefully, now you understand how recursion works, and how you can use it.