Time and time again, you hear people say “Recursion is too hard”, or “Why do I need to learn recursion if it can be solved with iteration?” A simple Google search will find a vast number of questions asking why recursion is so difficult to understand.
So why learn recursion? Well, being able to think recursively is very important in programming for a couple of reasons:
Often solving a problem with recursion is cleaner and easier to implement than if you were to do it iteratively. A good example of where recursion is useful is in QuickSort algorithms.
It can be used to break down problems into smaller components — a recursive pattern known as Divide and Conquer. This is particularly useful for techniques such as MergeSort, binary search, and depth-first search.
Recursion is a fundamental problem-solving style and every developer should have it in their toolbox. You’d be surprised at how often recursion comes up in coding interviews, particularly at bigger companies like Google, Microsoft, and Facebook.
So if you’re heading into an interview and feel queasy about recursion, then it may be time to brush up on it, and we’ll help you.
Here’s what we’ll cover today:
Get the hands-on materials to learn recursion in any programming language.
{ // base case if (n<=1) { return n; } // recursive case else { return (fibonacci(n-1) + fibonacci(n-2)) } }
Here, we have the recursive function which contains two parts; the base case and the recursive case.
The base case of the function is being defined in line 5 where the function will terminate and return n
when the if
condition of n<=1
is met. In other terms, the base case is what terminates your program.
The recursive case comes next, or the function that we want to repeat until we have reached the base case. So if the base case condition does not evaluate to true, the function then enters the else
block (line 8-11), where it then recursively calls itself with the input arguments fibonacci(n-1)+ fibonacci(n-2)
, as seen in line 10.
Now, your interviewer will tell you something like, "return the nth element in a Fibonacci series.”
Your first solution would likely be the brute-force while
loop approach. This approach solves the problem but is not optimized.
So the interviewer asks, “how would you optimize this algorithm?” One way to do it would be through recursion seeing as you only have two variables (fibonacci n-1
) and (fibonacci n-2
).
They may ask a follow-up question such as, “how would you further optimize your recursive function?” One way to do this would be through memoization — a technique used to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
What is great about this example and the Fibonacci sequence is that it is a transition into some very useful techniques like memoization and dynamic programming.
If you’re in a technical interview and a recursion question comes up, it is always best to begin with the end in mind or the base case. There are two parts to a recursive function;
It’s important to remember that your base case ensures that the program will exit. Otherwise, your program will run infinitely.
Remember back to the days of probabilities and word problems? How they taught you whenever you heard the word “and” you would multiply the probabilities and “or” meant you added them. This concept has some similarities to programming and in particular recursion.
A really good indication of when you should use recursion is when you hear concepts such as “tree”, “graph”, “linked list”, or “nested”. These are almost dead giveaways that you’ll need to perform some recursive function.
If you’re being asked a technical question in an interview that deals with recursion it’s important to be thinking about a few things:
Techniques
In order to feel comfortable in a technical interview, you must practice these concepts that are mentioned above. Here are a few sample problems you can work through and get you thinking about recursion:
Problem Statement:
Print a reverse linked list. Start off by keeping it simple. Try printing this linked list in reverse.
Problem Statement:
Depth-first search in graphs. This will get you familiar with traversal algorithms. Try writing some recursive code for this graph
Recursion produce cleaner, more efficient code, and demonstrates that you can think about problems in different ways.
There are a few things you’ll want to prepare for recursion interview questions:
Understand the basics: Understand why recursion matters, and where it’s useful and where it isn’t.
Convert solutions Iterative to Recursive: Practice converting unoptimized iterative solutions to optimized recursive solutions.
Practice: Practice makes perfect. Try writing out iterative and recursive solutions on a whiteboard and talk through how you did it.
To help you with these steps, Educative has put together a Recursion for Coding Interviews collection, with courses for all the top languages. Each course covers advanced recursion concepts and gives you hands-on practice with top recursion interview questions.
Happy learning!
Join a community of 500,000 monthly readers. A free, bi-monthly email with a roundup of Educative's top articles and coding tips.