Recursion: a short introduction
Probably, one of the most common examples of recursion in nature, can be found in ourselves and every single living being. It was the biologists, Humbert Maturana and Francisco Varela who in 1973 defined autopoiesis as an unique condition of living beings, where they can constantly produce itselfs at a cellular level (Varela & Maturana, 1973).
Also, in the art world, we can find examples of recursion from drawings containing a copy of itself, called the Droste Effect. And in music recursion can be represented with hierarchies which allows the generation of multiple levels with a single rule (Dias Martins & Tecumseh Fitch, 2017).
As you can see, and if we go deeper, we could say recursion is more like a process related to life and nature. However, this blog has nothing to do with biology, but with computer science and its maths behind it.
In computer science, recursion can be described as a method of solving a problem where the overall solution is going to be the result of smaller solutions of the same problem (Dias Martins & Tecumseh Fitch, 2017). Normally, this is done recursively by using functions that call themselves, within its own code.
Now, many of the problems solved by recursion, can generally be solved by iteration. Also, using recursion causes functions to be called repeatedly from within itself causing the call stack to increment in the same size of the sum of the input sizes of all calls done, making the code less efficient from the memory management point of view.
Then, if the above is true, why use recursion over iteration? Well, basically because some problems are simpler to represent its solution recursively than implementing highly nested and complex code.
As recursion can also be understood as an iterative process of self call, this can go infinite as a loop.Then, in order to avoid infinite running of itself, recursive functions must obey two properties in order to work properly:
- Base criteria: it’s a condition that when met, the function stops calling itself. At least, there should be one base criteria in any recursive solution.
- Progressive approach: with each call the function does, the condition should make the recursive call come closer or approach the base criteria previously defined.
Implementation:
Now, lets see the next recursion example step by step:
As we can see from the example above, the problem is being solve recursively in small steps by solving the same problem while filling the stack memory, with information of each step. This is going to work until the algorithm reaches the base criteria, and the stack is going to be freed step by step, recursively while the solution of the previous step is being sent to the next, until it gets the first one.
Bibliography
Dias Martins, M., & Tecumseh Fitch, W. (2017, 01 01). Cognitive representation of “musical fractals”: Processing hierarchy and recursion in the auditory domain. ScienceDirect. https://www.sciencedirect.com/science/article/pii/S001002771730001X
Graham, R., Knuth, D., & Patashnik, O. (1990). Concrete Mathematics. ISBN 0–201–55802–5
Varela, F., & Maturana, H. (1973). De Máquinas y Seres Vivos: Una teoría sobre la organización biológica. Editorial Universitaria.