We’ve heard of this fancy thing called recursion and it’s like when things keep repeating or looping right? Almost like a circle? Or maybe it’s like a boomerang and it goes somewhere and comes back and you keep doing that. All of those answers are spot on, sort of aha.
Grab and some chai and let’s walk through recursion, odds are you have already used recursion unknowingly.
To keep it simple, recursion is calling a function within a function until a base case is met, or it could throw an error or runs infinitely, infinitely, infinitely… We’ll take a look at a code example shortly.
Is Recursion better than Iterative?
The opposite of solving something recursively is doing it iteratively, when you write a
for loop that’s usually iterative. Writing the same code but in a recursive manner is not more efficient by any means. The Big O notation for a solution written iteratively or recursively will output the same, under the hood for a software engineering examination, you will actually see that recursion will actually add a lot of function calls, but that’s usually no problem.
If it’s not more efficient what’s so good about recursion?
Recursion does not add value to the program output and rather how a developer digest the code they’re reading. Remember that in software development, a large part of our time is spent reading other peoples code and even our own code and trying to piece together what it’s doing. In the coming examples I show you it will be clear that writing code recursively tends to be much drier than writing it iteratively.
Instead of calling a big old for loop, you’ll have a base case, edge case(s) and another cases where the recursion happens. Let’s take a look at a code example that is a factorial function so if the given argument of the function is 5 our program should execute 5 * 4 * 3 * 2 * 1 = 120 as our result.
At first you might think, let’s loop through the range of the input and keep track of a sum result which we append each number to until we reach n (the number we’re given). This is O (n) time complexity where n represents the size of the number given to the function, in our case above: 5, but it also could’ve been 5 million aha.
def factorial_iterative(n): result = 1 if n == 0 or n == 1: return 1 for i in range(1, n + 1): result *= i return result
So that’s okay and all... But let’s do it recursively.
def factorial_recursive(n): # check if n is one of the base cases if n == 0 or n == 1: return 1 # check if n is an integer larger than the base cases elif n > 1: # call function recursively return n * factorial_recursive(n - 1)
So walking through this factorial recursive function, we take in a number, n and then we first check if n is 0 or 1 as then we’ll just want to return 1, that’s our edge case, being handled. Otherwise, let’s continue to see if n is greater than 1, if so, call our function within our function (RECURSION whoaa).
Breaking that recursive line down:
So we return n, let’s say n is 5 and we times is by the function call with n-1, so 4. So So really, we’re doing, n*4… and this is going to keep happening and what it’ll look like is 5*4*3*2*1 and then WHOA we hit our edge case so we stop.
Recursion if you draw it out, maps into a bunch of branches and it can get daunting when you get to more advance stuff but if you have this fundamental knowledge of how it works you can break down any problem!
Here’s a few more complex examples so you can wrap your head around it.
I’d like to dive into some more tree traversal code to more clearly show you Recursion in action. Let’s take a look at a post order recursive.
Here’s some code to accomplish that in just a few lines:
def _traverse_pre_order_recursive(self, node, visit):"""Traverse this binary tree with recursive pre-order traversal (DFS).Start at the given node and visit each node with the given function."""if node is not None: visit(node) self._traverse_in_order_recursive(node.left, visit) # Traverse left subtree self._traverse_in_order_recursive(node.right, visit) # Traverse right subtree
This function is 4 lines of code, you can imagine having to do this iteratively would triple the lines of code. While it would work and operate the same way, recursive code can often be much more developer friendly.
Now, I challenge you to find someone new to programming and share this article with them and then peer code a recursive problem and share your results down below in the comments! Please feel free to ask any questions or insert any constructive feedback into the comment below! And don’t forget to clap 👏🏼👏🏼👏🏼
Here are some more resources you can use to understand and visualize just how recursion works! 🎉
VisuAlgo - Recursion Tree and DAG (Dynamic Programming/DP)
This visualization can visualize the recursion tree of a recursive algorithm.But you can also visualize the Directed…
Visualizing Recursion - How to Think like a Computer Scientist: Interactive Edition
Some problems are easy to solve using recursion; however, it can still be difficult to find a mental model or a way of…
Thinking Recursively in Python - Real Python
"Of all ideas I have introduced to children, recursion stands out as the one idea that is particularly able to evoke an…
Recursion is the process of defining something in terms of itself. A physical world example would be to place two…
If you’re curious to know my name is Asim Zaidi and I am a software engineer specializing in frontend engineering. I used to study Computer Science at the University of Illinois at Chicago, this past summer I dropped out of the school to join the Make School Product College where I’ve been leveling up my software engineering skills like crazy. From writing complex Mongo queries in a Node Express app to developing state of the art React web applications utilizing Redux store management and local Storage for data persistence to learning and practicing teamwork and software product development to learning complex data structures like trees, graphs and more! I’m happy to be in San Francisco touching code every day and learning new things every day. Aside from coding I love music and community building. I run a digital creative agency, Tech Made and used to run a web app product called Bondfire. I’m currently searching for a fun and fast development team to join as well!
I’m out, I’m out, I’m out… 😜