4 ms·

I don't understand what's weird and special about recursion other than the ways it can be used to easily solve some problems. I would find it very unintuitive

I don't understand what's weird and special about recursion other than the ways it can be used to easily solve some problems. I would find it very unintuitive that in a language I couldn't write a function that calls itself. That feels like an obvious thing (if we ignore all the implementation details). When I first started programming I used recursion without knowing that it's called like that and I didn't expect it to be called in any special way at all.

bunderbunder 11y ago
One big practical complaint is that recursion makes it difficult to reason about the run-time characteristics of code. There's some truth to this - I'm personally no stranger to refactoring recursive functions that have proven susceptible to stack overflows into iterative implementations. I think even the most die-hard functional programming fans among us secretly know that this is a problem. It's why virtually every functional language implements tail call optimization, and why one of the earliest things that's taught to new students of functional programming is how to ensure that functions use tail recursion whenever possible. Sometimes we even go through some pretty impressive contortions because of this. Consider the case of continuation passing style. The other is that a lot of people find recursion hard to understand. Others seem to naturally think in terms of recursion and think iteration is a headache. I'm not sure the two camps ever see eye to eye. It might be a brain wiring thing. Though perhaps practice rewires your brain - I wouldn't be surprised if making someone spend a decade writing mostly imperative code causes them to become more comfortable with iteration, and making someone spend a decade writing mostly declarative code causes them to become more comfortable with recursion.
- Swizec 11y ago
  > I wouldn't be surprised if making someone spend a decade writing mostly imperative code causes them to become more comfortable with iteration, and making someone spend a decade writing mostly declarative code causes them to become more comfortable with recursion. I have spent a decade doing a mix of both. It really really really depends on the problem at hand what's easier to understand Have to traverse a tree? Recursion. Have to make a big thing out of small things? Recursion. Have to add +1 to a bunch of numbers? Loop.
- smosher_ 11y ago
  Fwiw I avoid writing both loops and recursion as much as possible. Collection data structures usually come with their own fold/map/etc functions, so this works well in practice.
munificent 11y ago
> I don't understand what's weird and special about recursion Here's one way to see why recursion is special. Look at it from the perspective of implementing the language. If your language doesn't have recursion, you can treat every local variable in your program as if it were a static global variable. It's local in terms of name scope, but you can give it a fixed blob of memory that you pick at compile time. This is exactly what early Fortran compilers did. foo()'s local variables go here, bar()s go here, etc. You can do away with the stack entirely, I believe. So, without recursion, you can make your entire program only use statically allocated memory. You can be sure it will never, ever ever run out of memory.
- sn41 11y ago
  Thank You for that interesting view. Do you have a reference for the early Fortran compiler design? I've always wondered why people say Fortran is blazing fast, even compared to C.
  - blt 11y ago
    From what I've read, Fortran's performance advantage over C is mainly due to a lack of pointer aliasing[1] which permits the compiler to optimize more aggressively. I am curious to know if modern Fortran compilers still use static allocation for local variables when compiling in Fortran 77 mode. I'd guess the cache advantages of keeping parameters close together in memory compensates for the extra work of manipulating the stack, but who knows... [1] https://en.wikipedia.org/wiki/Pointer_aliasing https://en.wikipedia.org/wiki/Pointer_aliasing
  - munificent 11y ago
    I don't offhand, but that's what the article is referring to when it says: > And this is what they wanted to remove because they wanted static allocation of procedure activation records. From what I can tell with a bit of digging, machines/compilers back then didn't even use return stacks for subroutines. Instead, they used self-modifying code (!). To return from a subroutine call, you'd do something like this: 1. When compiling a subroutine, add a JUMP followed by an address to the end. 2. When you call a subroutine, modify the code to change that address to point back to the callee. 3. Jump to the subroutine. 4. When it's done running, it hits the last JUMP and jumps back to the caller. With this, you don't need any concept of a call stack at all. But it obviously prohibits recursion since the later call would trash the earlier one's return address.

bunderbunder 11y ago

One big practical complaint is that recursion makes it difficult to reason about the run-time characteristics of code. There's some truth to this - I'm personally no stranger to refactoring recursive functions that have proven susceptible to stack overflows into iterative implementations. I think even the most die-hard functional programming fans among us secretly know that this is a problem. It's why virtually every functional language implements tail call optimization, and why one of the earliest things that's taught to new students of functional programming is how to ensure that functions use tail recursion whenever possible. Sometimes we even go through some pretty impressive contortions because of this. Consider the case of continuation passing style. The other is that a lot of people find recursion hard to understand. Others seem to naturally think in terms of recursion and think iteration is a headache. I'm not sure the two camps ever see eye to eye. It might be a brain wiring thing. Though perhaps practice rewires your brain - I wouldn't be surprised if making someone spend a decade writing mostly imperative code causes them to become more comfortable with iteration, and making someone spend a decade writing mostly declarative code causes them to become more comfortable with recursion.

Swizec 11y ago
> I wouldn't be surprised if making someone spend a decade writing mostly imperative code causes them to become more comfortable with iteration, and making someone spend a decade writing mostly declarative code causes them to become more comfortable with recursion. I have spent a decade doing a mix of both. It really really really depends on the problem at hand what's easier to understand Have to traverse a tree? Recursion. Have to make a big thing out of small things? Recursion. Have to add +1 to a bunch of numbers? Loop.
smosher_ 11y ago
Fwiw I avoid writing both loops and recursion as much as possible. Collection data structures usually come with their own fold/map/etc functions, so this works well in practice.

munificent 11y ago

> I don't understand what's weird and special about recursion Here's one way to see why recursion is special. Look at it from the perspective of implementing the language. If your language doesn't have recursion, you can treat every local variable in your program as if it were a static global variable. It's local in terms of name scope, but you can give it a fixed blob of memory that you pick at compile time. This is exactly what early Fortran compilers did. foo()'s local variables go here, bar()s go here, etc. You can do away with the stack entirely, I believe. So, without recursion, you can make your entire program only use statically allocated memory. You can be sure it will never, ever ever run out of memory.

sn41 11y ago
Thank You for that interesting view. Do you have a reference for the early Fortran compiler design? I've always wondered why people say Fortran is blazing fast, even compared to C.
- blt 11y ago
  From what I've read, Fortran's performance advantage over C is mainly due to a lack of pointer aliasing[1] which permits the compiler to optimize more aggressively. I am curious to know if modern Fortran compilers still use static allocation for local variables when compiling in Fortran 77 mode. I'd guess the cache advantages of keeping parameters close together in memory compensates for the extra work of manipulating the stack, but who knows... [1] https://en.wikipedia.org/wiki/Pointer_aliasing https://en.wikipedia.org/wiki/Pointer_aliasing
- munificent 11y ago
  I don't offhand, but that's what the article is referring to when it says: > And this is what they wanted to remove because they wanted static allocation of procedure activation records. From what I can tell with a bit of digging, machines/compilers back then didn't even use return stacks for subroutines. Instead, they used self-modifying code (!). To return from a subroutine call, you'd do something like this: 1. When compiling a subroutine, add a JUMP followed by an address to the end. 2. When you call a subroutine, modify the code to change that address to point back to the callee. 3. Jump to the subroutine. 4. When it's done running, it hits the last JUMP and jumps back to the caller. With this, you don't need any concept of a call stack at all. But it obviously prohibits recursion since the later call would trash the earlier one's return address.