Part 6 — Data Structures and Algorithms in Plain English | Recursion
It’s been three weeks since the last part (part 5). Huge apologies for taking so long before releasing this. Several restricting factors as regards trying to create a solution that will allow for inclusive and structured learning for just about everyone. But this is just how much I can tell you, we’ll all just have to wait till the product is released. Anyway, back to today’s topic… Recursion.
What do you know of the word recursion? Maybe you’ve heard it, said it, or even used it… it doesn’t exactly matter; what matters is understanding what it truly means and how you can take advantage of it to improve your computer algorithm.
In general terms,
Recursion can be defined as a process whereby a function calls itself directly or indirectly until it no longger needs to.
Let’s break it down even further…
Imagine you need to add the first n natural numbers in mathematics together (natural numbers are simply positive integers in mathematics… 1,2,3,4,5,6…). The solution you would think of is represented as such below.
Here, we start by manually adding the numbers altogether till we get to the nth number. This methods works, but once the value of n changes, our solution no longer holds and we just have to start again.
This simply means we are unsure of what n will be and we need a solution that keeps running till we become sure. This is where recursion comes in. And to solve this with recursion, here’s what we will do.
We keep calling the function inside of itself and the function, by itself, knows when to stop since already told it to stop calling itself when it reaches the point where n becomes less than 1.
Here’s a breakdown of how it is working.
Now, whenever our value of n changes, the codes keeps running until it becomes sure of when to stop. With this in mind, we can go on to define recursion in another interesting way.
Recursion, in plain English, simply means we can’t really be sure of anything until we actually are.
The idea behind recursion involves breaking a problem down into smaller cases while including certain base conditions that help in stopping the recursion when necessary.
A function that calls itself is called a Recursive Function
Recursion can be classified into two as follows.
- Direct Recursion
- Indirect Recursion
A direct recursive function is a function that calls itself directly inside of itself. An example is our above add_num function.
An indirect recursive function is one that calls itself inside of another function called inside of itself. Yea, I know that’s a mouthful which is why we have an example below.
Now you get it… function one is calling function two which is, in turn, calling function one again recursively.
Recursion and Stack Overflow
No, not the Stackoverflow you visit to find solutions. Remember from the breakdown of our add_num recursive function that we talked about things being saved to memory?
The reason we have base conditions to help stop our recursive code is to avoid what we call Stack Overflow.
Stack Overflow is a situation whereby a recursive function keeps running till the computer runs out of memory.
An easy way to illustrate this is by setting a base condition that will never be met.
Notice how we defined a base condition of n equal to 10 but called our function with the value of n being 6. This means that no matter how our functions run, it will never get to 10. It will change value from 6 to 5, 4, 3, 2, 1, -1, -2, -3, -4, … infinity. Eventually, the computer will run out of memory and the code will break off.
There’s much more to the memory stuff (explaining them will make things super technical for you) but the most important parts to know are those we’ve covered here… in plain English.
And that’s it… recursion in plain English… memory, stack overflow (call stack overflow), direct recursion, and indirect recursion. I believe you’ve gained another new insight into the world of DSA (data structures and algorithms).
In the coming parts, we’ll be taking a look at how we can implement recursion in our Binary Search Algorithm and how we can use Binary Search to find a word (string) from among a list of sorted words.
For now, try writing a recursive algorithm to print the nth Fibonacci series. You can always send your solution to me via https://samperfect.me
Thank you for reading and don’t hesitate to clap out loud if this series has inspired you so far.
