As you all know, when we have a repetitive task that needs to be implemented several times we are using …. ? what? Yes, you are right we are using loops. Now sometimes for some problems and algorithms using loops will complicate things rather than helping us to reach the final result. For this we have another technique we call it (RECURSION).
- What is recursion?
- What is a recursive function
- Parts of a Recursive Algorithm
- Can we use recursion with loops?!
What is recursion? Unfortunately, like most programming concepts, when you google "recursion" the definition can be a bit confusing.
"Recursive – refers to or contains programs or routines, some of which require full application, so their explicit interpretation usually requires many consecutive executions."
If this confused you, don’t worry; because the concept isn’t as complicated as the incredibly bombastic wording might make you believe. The idea of recursion is actually very simple: a function that calls itself which means
defining a problem in terms of itself. Well, putting that principle into practice to write something useful is another bean bag.
Let’s take a look at the following functions.technically this is a recursive function, but it’s
missing a very important element.
Try running this function in an online editor like repl.it and see what will happen (do not test in console) … Did you try it?Not yet, then go and try it😉
Let’s see how it works?
- This countDown function takes in an initial number and, well, counts down.
- Each successive call decreases the number and logs it to our console.
- What do you think the problem in this approach? The only issue is that there is no end to this recursion!🤔
(nothing will stop it); which means an infinite recursion that will crash your program or browser and freeze your computer.
If you actually executed this method in the browser you would create a stack overflow.
A stack is a data structure that the browser uses to keep track of called functions, once the function is ready to be invoked, it is popped off the call stack.
You can think of the stack data structure as a stack of plates, where the last plate on the stack will be the first to be taken off, conversely, a queue data structure is similar to a line to a concert, where the first person in line will be the first inside.
The stack can only handle so many functions being heaped on it until it falls over like some comically tall stack of plates being carried by a waiter. Recursion fails.
All the recursive function should have the following :
A base case (stop condition)
A recursive condition
- The recursive condition triggers another call of the function
- while the base case returns from the function, popping it off the stack.
Let’s explore a much more useful problem that can be solved with recursion:
The aptly named flattenArray does exactly what the name suggests.
- It flattens the damn array!
- Pass an array containing an unknown number of nested arrays nested at various levels
- and return a single array containing all contained elements.
This kind of problem immediately comes to mind as a problem that should be solved using recursion. Why? This is because we don’t know how many nested arrays the argument will contain, or how deep they can be nested.
A for loop doesn’t meet our needs here, but it definitely solves the same problem over and over again. Recursion should also be considered first.
Problems that can be solved recursively can often also be solved iteratively using work queues and while loops.
The reason I often use recursion over iterative solutions is for readability and ease of use. A recursive solution is often easier to write.
Looking back at the flattenArray method, we see that it only supports two cases.
- That is, whether the element you are looking at is an array. If the current element is an array, recursively call the function and push the unstructured result into the final array.
- If the element is not an array, push it to the last array.
When you start writing a recursive function, you may want to think about each call to understand what is happening at each iteration.
Personally, I find this confusing, but you might too.
My advice is to break down the problem you're trying to solve into its most trivial form. For example, in the problem above, we only consider whether the element is an array, and flatten it if not. This approach to determining the simplest subproblem requires a small amount of confidence that recursion works, and that confidence takes some time to build. The more problems you solve with recursion, the more you get a feel for when and where to use it. If you need to see what happens on each iteration, add a debugger statement above your recursive case and inspect the call stack in your browser to get a more detailed view of the current value of the local scope, See how the call stack grows:
Don’t be scared of recursion. It’s yet another tool in your developer tool box and it can help you solve complex problems you may encounter at work and almost certainly in any interview for a highly coveted tech company 😉.