Recursion
A distribution is a mathematical description of a random variable's probability space.
A distribution is a mathematical description of a random variable's probability space.
Fractals are perhaps the primary example of using recursion to model patterns in nature. Most fractals begin with very simple rules that describe how they are generated; in this case, we take one side of each of the smallest squares and create two smaller rectangles out of that. Theoretically this process can repeat ad infinitum, although fractals in nature, such as Romanesco broccoli, will stop due to natural constraints. In this example, by looking at each of the smaller branches in the tree, you'll notice that it has a similar structure to the fractal as a whole, hence the recursive aspect. Try pressing the "Grow tree" button to see this in action.
In computer science, recursion provides an elegant but scalable framework to model problems of arbitrary size. For instance, to model the problem of finding the length of one of the above fractal's squares, we can create a recursive tree as shown here. The root node at the top denotes the side length of the largest square; its two chidren the side length of the two main branch squares; and so on and so forth ad infinitum. (Here the recursive tree is truncated for sake of clarity.) Just as the fractal was recursive because every branch had the same structure as the main branch, every subtree of this tree bears similarity to the tree as a whole upon expansion, hence the recursiveness of the tree. Other recursive data structures commonly used in practice include linked lists and tries. Try expanding the recursive tree to find a subtree node length and notice the structural similarity at every level of the tree.
When recursive algorithms are run without optimizations, the recursive trees can become so large that the algorithm cannot hope to finish in a reasonable amount of time. One optimization to combat this is called dynamic programming. In dynamic programming, rather than fully explore a recursive tree, we can reuse previous results if our current branch's state has been computed before, a technique more formally known as memoization. In this example, we calculate Fibonacci numbers using the recursive relationship $$F_{n + 1} = F_{n} + F_{n - 1}$$ with n = 0 and n = 1 being our base cases, and we can reuse stored Fibonacci numbers rather than rerun our algorithm on a smaller tree. As you can see with the purple nodes, this can dramatically collapse the number of nodes traversed into a much more reasonable number. Try pressing "Calculate Fibonacci" to see dynamic programming in action. Can you guess what the runtime of calculating Fibonacci numbers using dynamic programming is?