Hacker News Reader

Comment by munchler | Hacker News Reader

Recursion is a trick. It’s a beautiful, elegant, concise trick, but it’s not at all intuitive to most humans.

The problem with for loops isn’t the loop. Loops are easy to understand. The problem with for loops is that you have to maintain mutable state across iterations, which quickly gets very complicated. Recursion is useful specifically because it doesn’t need mutable state.

View on HN

Instead you need to understand induction, which is non trivial as well..

Yes, but induction and recursion are essentially the same thing. If you understand one, the other is pretty obvious.

I think recursion is incredibly intuitive if you just start with an obviously recursive data structure. Give someone a tree, and writing a recursive function is a very natural thing to do.

Lists are an even simpler recursive structure, but people really struggle with the idea of head vs. tail. Using a for loop to iterate a list is way easier for beginners to understand. Even experts usually prefer a list comprehension over explicit recursion.

The stack pointer is as much mutable state as the loop index.

Sure, which is why high-level languages manage the stack pointer for you. You can get a long way with pure functional recursion before you have to worry about annoying details, like tail calls and stack sizes.

And the RAM your computer is writing everything to is mutable! And someone could come along and bash your computer with a hammer -- it would feel awfully mutable then! Everything is mutable if you consider the upcoming heat death of the universe.

The point is that within the abstraction you're working in, recursion is entirely immutable, and loops are not. Good programmers selectively forget about stack pointers and RAM and the heat death of the universe when they're writing code -- they put on the correct "costume" for the part of code they're in and they never go "out of character". Worrying about the stack pointer is like having your Starbucks cup in the shot of Game of Thrones. Danaerys Targaryen doesn't know WTF Starbucks is and your programming avatar should not know WTF a stack pointer is.

A language with a "stack pointer" would indeed be difficult to learn.

Reply on news.ycombinator.com