Understanding Recursion
What Is Recursion?
In definition terms, a Recursion is a process of a function that calls itself “directly” or “indirectly”. Or in other terms, a function that calls itself is recursive; hence where the term recursion came from is the act of using that function. As for the history of recursions, it is best to talk about what the word means. Recursions come from the Latin word ‘Recurere’ as in to run or hasten back, return, revert, or recur. Like most functions in Python or coding in general, recursions are a technique to help you reduce the length of your code and make your code easy to read or write.
In more basic terms, you can break down a code and make It into smaller parts or create more minor problems you can solve.
Examples
I know what you think. If Recursion is just a function to repeat itself on and on in a program, couldn’t the code continue and never stop creating the same code? Possibly creating an infinite code and wasting all your memory in your computer. Yes, you are correct, but that is why there is a Recursion error. For instance, as simple as code like:
Def function():
X = 10
function()Based on that code, your computer can only interpret and act on that code so many times it has a limit, so it will just give you a “RecursionError”. The idea is that recursions help you demonstrate your problem in one or smaller issues so you can add one or more base conditions to stop your problem. A notable example of this is when you want to add numbers to each on a function like “f(n) = 1 + 2 + 3 + 4 +…. + n” n being a natural number that comes after the other as eight comes after 7, 16 comes after 15. 1027 comes after 1026. The code would look somewhat like this:
f(n) = 1 + 2 + 3 +………+ nBut except for going on and on, wasting your time writing code until you get to the number 127, you can write the code:
f(n) = 1 n=1
f(n) = n + f(n-1) n>1In the code, the function acts on the last number that is interpreted, so except for writing 1 + 2 + 3 + 4… you find an easier and more efficient way to write it.
A base condition stops the code from going on and forever, basically a finish line or end goal for the code. For instance, a legend with a base case or condition would look something like: (this is an example from GeekforGeeks)
int fact(int n)
{
if (n < = 1) // base case
return 1;
else
return n*fact(n-1);
}This return function would be your base condition, giving you an end goal of where you want to stop n such. This code seems super simple, but programmers use this tool more than you think. With such a simple task to add numbers on top of each other, it is best to know the Fibonacci sequence because it has the same idea as Recursion. The Fibonacci sequence is a type series that usually starts at 0 and 1, and you generate numbers based on the sum of the last two numbers, for instance,
0, 1, 1, 2, 3, 5, 8, 13, 21, …Fibonacci
If we get into the Fibonacci sequence of a general idea of how recursions work, it is necessary that you also know how it works and how it solves problems. And when first learning how to use Recursion in Python or just coding in general, the Fibonacci sequence is an excellent illustration of that. A fitting example problem is the Towers of Hanoi(TOH). The Towers of Hanoi or “TOH” is a mathematical puzzle where you have 3 rods and disks, like this. The objective of the puzzle is to move the entire stack to another rod, but you cannot just lift all the disks at once and put them on another rod; there are rules.
The rules are:
1. One disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack; i.e., a disk can only be moved if it is the uppermost disk on a stack.
3. No disk may be placed on top of a smaller disk.
The code in Python would look something like this:
# Recursive Python function to solve tower of Hanoi
def TowerOfHanoi(n , from rod, to_rod, aux_rod):
if n == 0:
return
TowerOfHanoi(n-1, from rod, aux_rod, to_rod)
print("Move disk",n,"from rod",from_rod,"to rod",to_rod)
TowerOfHanoi(n-1, aux_rod, to_rod, from_rod)
# Driver code
n = 4
TowerOfHanoi(n, 'A', 'C', 'B')
# A, C, and B are the name of the rodsNow you might have a better understanding of recursions, but you should be able to see now that there are plenty of problems when using recursions. You learned this simple idea as a child, but writing it as a code is much more complex. An informative video to illustrate this is on GeeksforGeeks.org.
You see that the code might be simple and very intuitive as it is, but it can take time to grasp and understand the idea behind it genuinely. There is a great chance you run into infinite conditions because that is what most programmers run into when using recursions. For instance, let us say you are cleaning your car, and it is your first time using a different soap brand; the instructions say, “rinse, wash and repeat”. If you follow those rules, you will be washing your car forever. But thankfully, there is that one instruction that tells you to repeat those steps until necessary, which gives you that termination condition that “return” or end goal for you not to be washing forever.
If it were a robot and you forgot to add in a return function or end goal, that robot would be working forever. That is why it might seem so minor, but it’s a common mistake that programmers run into. Realpython.com does an excellent job of explaining how a recursion work by breaking it down into the pattern it follows:
- One or more base cases are directly solvable without requiring further Recursion.
- Each recursive call moves the solution progressively closer to a base case.
Disadvantages
Having an infinite function problem (Recursion Error). But there is a lot more to it. For one, the memory space it takes, a lot of memory and time is taken through recursive calls, which makes it expensive to use.
There is also something called a related run time error. When a recursive call is made, a new stack frame is created(every stack needs memory). You must correctly include a return statement terminating the code to stop to avoid running out of memory.
Even though using the recursions function helps you break down the problem and make more minor problems, you may need to catch up in the code and lose track of stacking and actions the code is causing. Also, you will run into the challenge of debugging the code. Lastly, the reasoning behind recursions can be challenging to wrap your head around, but if your calls are not terminated, you can form an infinite loop.
When to use Recursions
Usually, when you find yourself in a situation where you have a problem, it is too big to deal with all at once. Recursions break down your program and make your problems into “smaller problems.” For instance, problems that can be solved with Recursion include: calculating the factorial of a number, finding the nth Fibonacci number, traversing and printing the elements of a binary tree, and more.
When you should not use Recursions
It would be best if you did not use recursions when you can quickly solve the same problem using an iterative approach. Recursions can be slow and consume a lot of memory as they involve function calls and stack frames.
What’s the difference between Loops and Recursions?
You should see a lot of similarities between Recursion and Loops; it is said that almost all recursive functions can be rewritten as loops and vice versa. A straight definition would be “recursions is a method of calling a function within the function, as for loops it’s a controlled structure that allows executing a block of code repeatedly within the program” — pediaa.com. It is commonly known that recursions are less understood because of the complex code that it has to break down into sub-problems(as you know), “a continuous loop of the problem” Georgiev says it perfectly.
A Recursion code might look like this:
Item Search(string desired, Scope scope) {
for each(Item item in scope.items)
if(item.name == desired)
return item:
return scope.Parent? Search(desired, scope.Parent) : null;
}
Vs. code with Loops would look like this:
Item Search(string desired, Scope scope) {
for(Scope cur = scope; cur != null; cur = cur.Parent)
for each(Item item in cur.items)
if(item.name == desired)
return item;
return null;
}If you compare the two through real-life situations regarding speed and efficiency, loops have the upper hand. Recursion execution is slower, and Loops executes in a faster efficient way. Recursions also use a stacking method to store the local variables when the function is called (loops do not operate on this function). I have said this earlier in the paper, but in the case of memory and space complexity, loops beat recursions because of how much space is required for recursions. In terms of code readability, of course, this depends on the level of understanding a programmer has, but it is known that a code with recursions is more readable than a program with loops.
Takeaway on Recursion
There is a joke that goes on to understand. Recursion entirely means smiling at the joke that “to understand recursion, you must understand recursion.” If you know, you know, but I would like to say overall, this technique of not only being able to understand recursions fully and to be able to use this code function not only give a better and easier time as a programmer. But it will make you a better programmer and coder when you master this skill.
The recursive function is being used to this day, but programmers now might need to gain the critical knowledge that is behind all of it. Through all this, in the programming world, “everyone wants to work smarter, not harder,” and if one wants to do that, one might have to consider using recursions in their code.
