What is a recursive Algorithm
What is a recursive Algorithm?
Recursion is made up of smaller versions of itself and a recursive algorithm calls on itself to solve problems this can be directly or an indirect call (Eck, 2017). Professors Cormen and Balkcom (n.d.) from Khan Academy put it in a great way…its like Russian nesting dolls. It’s using itself, within itself, but a smaller version of itself, until you get to the smallest version that you can’t break apart anymore.
Advantages?
It can be more powerful than iteration, when used appropriately.
In its history, its something that stems from mathematics, so its something that’s been around forever. Which makes it a little easier to grasp when you think about it mathematically.
Another reason that I noticed as an advantage, is that it’s a cleaner code to use recursion over something else. As its calling something from within itself, there is less code to write. It also, allows you to keep it cleaner when you are writing your pseudo code by allowing you to break it into pieces to solve. Now granted, I haven’t used it enough to know if a cleaner code is consistently correct, but from what I saw, personally it is.
A simple example is that of a factorial:
On paper or math, it would look like this:
5! = 5x4x3x2x1
N! = nX(n-1)x(n-2)x(n-3)…until you get to the smallest # of itself, which in this case is 1.
Normally we would code this using a loop, something that looks like this snippet:
An example of this, where in code it calls itself is
Disadvantages?
Something I realized right away from our readings is that it seems easier to get stuck in an infinite recursion, or stack overflow, which in turn can cause a program to crash.
To avoid this, all one needs to do is go back to their pseudo code and realize what the base case is. The base case, according Sedgewick and Wayne (2016) is the smallest value that you tell your code to use. This is the smallest piece and once we have that, we can ensure that a recursion can stop.
Resources:
Cormen, T., ; Balkcom, D. (n.d.). Recursion. Retrieved November 25, 2018, from https://www.khanacademy.org/computing/computer-science/algorithms/recursive-algorithms/a/recursion
Eck, D. J. (2014). Introduction to Programming Using Java (Ver. 7). Geneva, NY: Hobart and William Smith College. Retrieved Nov 18th, 2018, from http://math.hws.edu/javanotes/
Sedgewick, R., ; Wayne, K. (2016, August 02). Your first recursive program. Retrieved November 25, 2018, from https://introcs.cs.princeton.edu/java/23recursion/
