Iteration vs. Recursion

Loops.

If you have spent any time working on algorithms and/or problems that call for multiple solutions, you are probably familiar with the eponymous concepts. While they are often used interchangeably due to the fact that they both engage in repeated execution of a given set of instructions, there are differences between iteration and recursion that are helpful to know when deciding on how to approach a problem.

First, let’s quickly go over the definitions. Iteration is the process of repeating an action (or any kind of instruction) until a certain condition (or value) is met. It is commonly implemented using a for or while statements in a loop. Recursion on the other hand is implemented in functions as a method that essentially calls itself over and over again. Like iteration, its execution depends on a condition that has to be satisfied in order for the recursion to end. This condition is called a base case that may or may not be reached.

Here is an example of a problem that can be solved both iteratively and recursively. Imagine that you need to write an algorithm that calculates a factorial of an integer n.

See the recursive solution below, followed by the iterative solution:

function factorialRecursive(n) {
 if (n) === 0 {
  return 1;
 }
 return n * factorialRecursive(n-1);
}
function factorialIterative(n) {
 let answer = 1;
 for (let i = 0; i <= n; i++) {
  answer = answer * i;
 }
 return answer;
}

As you can see, recursive solutions tend to look neat due to the smaller code size. Recursion is commonly used by functional programming languages, such as Haskell (the most beautiful language, IMO. Haskell is king.) Some people also find recursion to be more intuitive than iteration, which is used by imperative languages (e.g. Ruby). However, recursion generally has very high time complexity and is expensive memory-wise, as memory space gets taken up each time the function is called. This, as well as potentially infinite recursion, can lead to stack overflow, which can be dangerous (enough to stop NASA from using it in their code!).

I hope this was informative and helpful to those exploring the concepts of recursion and iteration. When deciding on which is better to use, the answer mostly depends on your data structure and time/space concerns.