Recursion vs. Iteration
Understand the fundamental differences between recursion and iteration, including their processes, memory usage, and performance impacts. Learn when to choose recursion or iteration for solving programming problems, with examples like quicksort and simple loops. This lesson prepares you to efficiently transform and apply these techniques in your coding interviews.
We'll cover the following...
What is iteration?
Iterative code is a block of code that runs in a loop. In other words, the same code is repeated over and over again. The idea seems much similar to that of recursion. So where does the difference lie?
Is there a difference?
Within recursion and iteration, there are multiple differences. These differences give these two implementations of repeated code their own uses.
-
The first difference to note is that recursion is always called on a function. Therefore, it is called a process. On the other hand, iterative code is applied on variables and is a set of instructions that are called upon repeatedly.
-
Recursive code will terminate on a base case condition whereas iterative code will either run for a particular number of loops or until a specified condition is met.
-
An infinite recursion can lead to the system crashing whereas with iterative code, it will just consume more CPU cycles.
-
Recursive code has an overhead time for each recursive call it makes, unlike iterative code.
-
Recursive code is smaller and neater in length than iterative code.
-
Recursive code is slower than iterative code as it not only runs the program but also has to invoke stack memory.
-
Recursion uses the stack to store the variable changes for each recursive call, whereas iterative code does not.
Does the difference matter?
Recursion provides us with neater, more concise code but more than that it gives us the advantage of a stack that tracks all memory changes. For this reason, in problems like quicksort, recursion becomes a better solution as the recursion stack makes it easier to implement the sorting algorithm.
On the other hand, iteration is faster and more useful to solve simple problems like printing a string letter by letter, where the recursion stack just takes up extra memory.
One cannot conclude which is better than the other in absolute terms, as each has its own purpose. The problem to be solved must have its own limitations and freedoms within which one has to decide which style works better.
Now that we have learned the differences between recursion and iteration, the next lesson will show you how to transform code from one form to another.