Recursion - what, why & how

tl;dr Recursion has real-world benefits, not just to impress interviewers with recursive fizz-buzz or Fibonacci answers.

Recursion Overview - The What

One way I have heard recursion explained is looking into a mirror and with another mirror behind you, visually showing you a reflection, reflecting a reflection...so on Ad Infinitum.

The metaphor aside, we can just think of recursion for this article's situation as a function that will call itself until a condition is met.
We will eventually show some examples of how to implement recursive functions.

Recursion Benefits & drawbacks - The Why

Some Pros:

• One of the benefits of recursion is it can potentially reduce Big O of time, here is a table with different levels of time complexity. In other words, it can potentially increase performance. (Edit: Caveat to this is utilizing memoization when possible.)

• So one of the things I like about recursion is its ability to reduce the surface area of code being executed especially if the inputs are uncomplicated. This can simplify the code at times and even make debugging and testing a bit less challenging.

• Uncomplicated inputs with repetitive tasks can be distinctly expressed and self-contained.

Some Cons:

• So as I mentioned recursion uses memory, in JavaScript, in particular, the call stack is utilized, in which maximum call stack can be reached.
  So while a recursive function is running it will retain the values in memory until it is completed.

• If unsuccessfully implemented then it can be slower than iterative approaches.

• Too many inputs can lead to more complicated termination conditions and recursive inputs.

Examples - The How

This recursive function finds an element in an array then constructs an object that gives the index of the found element in the array and a copy of the original array.

const numAr = [1, 2, 3, 4, 5, 6];
function numCheck(termN, arrCh, i) {
  console.log(i); // 0, 1, 2, 3
  if (termN !== arrCh[i]) {
    return numCheck(termN, arrCh, i + 1);
  }
  return { number: arrCh[i], indexOf: i, copyArr: [...arrCh] };
}
console.log(numCheck(4, numAr, 0)); 
// { number: 4, indexOf: 3, [1, 2, 3, 4, 5, 6] } 

This is a great mathmatical operation that can be expressed with recursion, since there are not very many inputs.

// GCD = Greatest Common Denominator 
 function gcd(x, y) {
  if (y === 0) {
    return x;
  } else {
    console.log(x); // 123432, 120, 72, 48
    console.log(y); //  120, 72, 48, 24
    return gcd(y, x % y);
  }
}
console.log(gcd(123432, 120)); // 24

I might figure out a nice example of tree traversal, nodes or some other structure searching

Comments

[David Wickes]

One of the benefits of recursion is it can potentially reduce Big O time.

Could you explain this a bit more? It seems like a pretty big claim, and it doesn't jibe with my understanding of the subject.

[Jacob Evans]

I couldn't find my previous resource but this has an example of recursion implementing memoization to reduce Big O complexity. It may be that it is possible to memoize the iterative approach as well and it's just easier to utilize recursions use of holding memory to make it easier or more efficient.
stackoverflow.com/questions/134400...

[Jacob Evans]

I'll link the resource when I get a chance to get on my computer.

A quick overview of it would be one way of reducing Big O of time is memoization, however, the cost of Big O memory (which is already high with recursion) increases even further.

[Jacob Evans]

I'm also more than happy to be proven wrong, or dive deeper into this together and discover more on it 😁

[hidden_dude]

I think Recursion is better sometimes because it can make somewhat complex algorithms seem simple. For example, QuickSort or MergeSort are quite easy to express recursively. They are much harder to read when written in non-recursive ways.

The Big-O complexity has little to do with recursion, since anything that can be written recursively can be written non-recursively (though it would look horrible in some cases).

A big danger of recursion is using it in languages that don't optimize away the stack (most popular languages) as well as hidden Big-O memory usage.

For example:

function sum(n) {
if (0 >= n)
return 0
else
return n + sum(n-1)
}

Uses O(N) stack space (assuming a language that optimizes away the stack). Whereas:

function sum(n,total)
if (0>=n)
return total
else
return sum(n-1,total+n)
}

Would use O(1) extra space in a language like Scheme.

[Jacob Evans]

Well said. I certainly don't consider myself an expert in Big O related things, I just read during my research it can be more efficient than an iterative approach in some instances where memoization can be utilized.

It wasn't 100% clear to me but enough to add it in as a possibility.

Love your comment though very insightful! Thank you 😄