Recursion: Scary words in programming, episode 4

Welcome to episode 4 of Scary Words in Programming!

scary-words-in-programming-with-pam

Recursion

I asked for suggestions for scary words, in particular words that scared people when they first started programming, and someone mentioned recursion.

When I think recursion, I think “super cool!” partially because I was indoctrinated in computer science by the instructor showing us art, in particular, art by M.C. Escher, whose art was inspired by mathematics. A visual example of recursion is the Droste effect, or pictures inside pictures inside pictures … (turtles all the way down!).

escher035

So, that probably didn’t serve to make recursion less scary, but I do hope that it’s cool.

Back to recursion’s unscary meaning. The basic understanding of recursion for programmers is “a function that calls itself” (pictures inside pictures). And furthermore, if you’ve already gone and understood for loops, you can easily understand recursion.

for(var i=0; i<10; i++) {
  console.log(i);
}

function coolFunction(i) {
  if (i < 10) {
    console.log(i);
    return coolFunction(i + 1);
  }
}
coolFunction(0);

In the for loop, I set up the loop with my initialization statement, my condition, and my increment. When I wrote coolFunction, I made my initialization statement a parameter, and then call the function itself to iterate through the numbers. coolFunction is technically “tail recursive” because the last thing it does is call a function (using the return keyword, so it literally can’t do anything but return the result of that function call).

And I’ll say it because every other post I read to triple check this stuff said it: tail call recursion can be “dangerous” without tail call optimization (TCO), which means your compiler/language doesn’t open new stack resources every time you make a recursive call – that if you call the function itself, the compiler/language should be smart enough to not allocate new resources. TCO is scarier to me than recursion, but I think I got a handle on it. That said, I don’t worry about it, because I don’t operate at the level at which avoiding recursion matters, and sometimes recursion is the most elegant/efficient solution (plus, ES6 is supposed to have TCO, so … no worries?).

To recap how unscary recursion is – when the function calls itself, that’s recursion (and it makes some cool art!). As I get more into functional programming, I expect to use recursion more, but it’s definitely something every developer should have a basic understanding of conceptually.

Be Sociable, Share!

Tags: ,

One Response to “Recursion: Scary words in programming, episode 4”

  1. Ken Dale October 22, 2014 at 6:03 pm #

    https://www.google.com/#q=recursion

    😀

Leave a Reply