Member-only story
Recursion 101
Solve problems recursively by taking it one step at a time
Welcome to Recursion 101. By the end of this piece, you will have a deeper understanding of solving problems recursively and also of a relating data structure. These are some of the heavier topics in the programming world, and newer programmers often dread the word recursion. Although it would be nearly impossible to explain all these concepts in depth in a single article, you will obtain a stronger grasp of recursion and why understanding a bit about data structures will aid in the overall picture. Like many things you first learn in programming, it seems difficult. But if you take it slow and understand the fundamentals, you’ll realize it’s nothing to be afraid of.
Stack
I believe the stack is an essential building block to understanding recursion. A stack is known as an abstract data type(ADT). An abstract data type means it’s a logical way of picturing data and ways to manipulate the data without going into detail of how it will be implemented. A simple way of remembering this is that an ADT answers the question, what does it do? The actual implementation of an ADT, known as a data structure, answers the question, how does it do it? The how would be represented by the actual programming of the methods detailed by the ADT. ADTs are language-independent. Because it doesn’t specify how it needs to be done, it can be written in any language.
A stack models the behavior last-in, first-out (LIFO). As the name stack implies, imagine a stack of blocks. You put several blocks on top of one another. To remove a block safely without destroying the stack, you remove the one on top, which is the last block you placed. The stack ADT works the same way. You can only remove items you place on a stack in the reverse order you placed them on the stack.
The Call Stack
Perhaps without even knowing it, you’ve been using a stack in all of your code. Your program uses a stack to control the flow of subroutines and to return control to the correct part of your program after certain procedures are performed.
