1 min read
Basic Recursion With Examples
Last Update: 14 September, 2022§Let's Start with A Description
Recursion can be simply explained as a function repeatedly calling itself until a condition is met. It can look daunting to beginners but when used properly they are much more performant than the iterations.
Considering that we call the same function over and over again, we make our code definitely shorter, clearer and definitely easier to read and understand.
We gotta be careful when we create a recursion, otherwise we can easily create and infinite loop.
Each time the function calls itself another stack is created and until the condition is met the stack wont be removed. This causes recursions to use more memory. The values created in the stacks are kept in the memory this way. Until the base condition is met stacks keep piling up. When the base condition is met stacks are cleared from the last to first. This means the last stack added is removed first.
As each recursive call creates a stack in the memory you as a programmer need to be careful about not causing a stack overflow. It can be explained simply as your program using much memory than it's supposed to. If you wanna go deeper than that check out here. This is one of the simplest explanations that I could find.
§Practical Examples
Well known and easy to handle problems using recursions are probably the Fibonacci Algorithm and finding the factorial.
function factorial(x) {
// Base Codition
if (x == 0) return 1
else return x * factorial(x - 1);
}
function fibonacci(num) {
// Base Condition
if(num === 1 || num === 0) return num;
else return fibonacci(num-1) + fibonacci(num - 2);
}
Pretty useful and concise if you ask me.
§The Advantages and Disadvantages of Using Recursion
As we can see from the examples above we can replicate the same functionality using iterations. They would be somewhat more understandable as well.
We need to also consider the fact that until the base case is reached, your stacks keep piling up. This means you will use much more memory than an alternative using iteration.
Tree traversals such as DFS and BFS algorithms rely on recursive solutions. You will see that the alternative is too verbose and harder to read and comprehend.
If recursion was a subject you have been avoiding so far, there you go! Now you got a basic understanding of why and how it works.
Ilker AkbiyikTable of Contents
Related Posts
