4 ms·

I found something like splitting a string into words not very intuitive... Also the classical (recursive) fibonacci function everyone shows has accidental comp

I found something like splitting a string into words not very intuitive... Also the classical (recursive) fibonacci function everyone shows has accidental complexity of O(2^n). If you want a sane version it looks definitely more complicated than the iterative version. I never saw a recursive version of bresenham's line plotting algorithm so this might be a good candidate as well ;)

chongli 6y ago
I found something like splitting a string into words not very intuitive... Just use a couple of accumulators (one for the current word, one for the list of completed words). Also the classical (recursive) fibonacci function everyone shows has accidental complexity of O(2^n). That's moving the goalposts. If you want a really fast fibonacci function then the classical iterative algorithm [which is O(n)] is not what you want either. Better to use matrix exponentiation which you can implement nicely with recursion using a divide-and-conquer approach similar to mergesort, giving you fibonacci with time O(log(n)). I never saw a recursive version of bresenham's line plotting algorithm so this might be a good candidate as well ;) There's nothing special about Bresenham's line algorithm that would make it particularly challenging to implement with recursion.
a1369209993 6y ago
> splitting a string into words not very intuitive It seems okay? split :: String -> [String] split s = w s "" where w [] "" = [] w [] a = [reverse a] w (' ':ss) "" = w ss "" w (' ':ss) a = reverse a : w ss "" w (c:ss) a = w ss (c:a) If you're done then you're done (and dump the accumulator), if it's a space get rid of it (and dump the accumulator), otherwise add it to the acuumulator. That the accumulator is stored backward is a bit wierd, but seems more a consequence of linked lists than recursion per se.
- the5avage 6y ago
  Yeah it's ok ;) Going back to my original comment this code is exactly what I meant with "patterns to deal with other problems". You clearly used a pattern (accumulator) with wich you are familiar. Do you agree that most imperative programmers would not come up with this solution on their own, if you didn't teach them the "accumulator pattern"? For me personally a tutorial with a lot code like that would be interesting. Showing me another version of a recursive descent parser doesn't teach me anything, because I know how to write it (with recursion!!!) in an imperative language...
  - chongli 6y ago
    Do you agree that most imperative programmers would not come up with this solution on their own, if you didn't teach them the "accumulator pattern"? Background: I’m currently working as a full time assistant for the first year computer science course at my university. We have around 1800 people enrolled in the class including over 1000 first year CS students. Many of our first years were exposed to imperative programming in high school, either at home or with a high school CS class. The course we teach is based on the book HTDP and uses a purely functional teaching dialect of Racket. Many of our students struggle to figure out how to use the different recursion patterns such as accumulative recursion and mutual recursion. I’m not the GP but I will answer your question anyway: yes, I agree that most imperative programmers would not come up with that solution. I have witnessed it myself first hand. Where I disagree is with any implication or suggestion that they should, given no prior functional programming experience. Accumulative recursion is a standard pattern in functional programming but if you’re an imperative programmer you may not have ever needed to learn it. Therefore, I think it would be unreasonable to expect you to come up with it on the fly.
  - a1369209993 6y ago
    > You clearly used a pattern (accumulator) with wich you are familiar. No, I didn't, and please refrain from imputing thought processes without evidence. I didn't even think the word "accumulator" until I got to the last paragraph and needed a term to describe the second argument to w. > Do you agree that most imperative programmers would not come up with this solution on their own If we assume most imperative programmers are idiots as a special case of most people are idiots, sure. I'm not sure that's a good assumption or particularly relevant, though. > Showing me another version of a recursive descent parser doesn't teach me anything Ah, I think I misunderstood your point, then: > > Which problems are hard to solve with recursion instead of iteration? > I found something like splitting a string into words not very intuitive... I assumed you meant that "splitting a string into words" was a example of a problem that was hard to solve with recursion (which I found rather puzzling, because as my example shows, it really isn't), rather than that it wasn't a good/intuitive example to illustrate recursion in the general case (which makes a quite a bit more sense, and I'm afraid I don't have a immediate solution to, sorry).

chongli 6y ago

I found something like splitting a string into words not very intuitive... Just use a couple of accumulators (one for the current word, one for the list of completed words). Also the classical (recursive) fibonacci function everyone shows has accidental complexity of O(2^n). That's moving the goalposts. If you want a really fast fibonacci function then the classical iterative algorithm [which is O(n)] is not what you want either. Better to use matrix exponentiation which you can implement nicely with recursion using a divide-and-conquer approach similar to mergesort, giving you fibonacci with time O(log(n)). I never saw a recursive version of bresenham's line plotting algorithm so this might be a good candidate as well ;) There's nothing special about Bresenham's line algorithm that would make it particularly challenging to implement with recursion.

a1369209993 6y ago

> splitting a string into words not very intuitive It seems okay? split :: String -> [String] split s = w s "" where w [] "" = [] w [] a = [reverse a] w (' ':ss) "" = w ss "" w (' ':ss) a = reverse a : w ss "" w (c:ss) a = w ss (c:a) If you're done then you're done (and dump the accumulator), if it's a space get rid of it (and dump the accumulator), otherwise add it to the acuumulator. That the accumulator is stored backward is a bit wierd, but seems more a consequence of linked lists than recursion per se.

the5avage 6y ago
Yeah it's ok ;) Going back to my original comment this code is exactly what I meant with "patterns to deal with other problems". You clearly used a pattern (accumulator) with wich you are familiar. Do you agree that most imperative programmers would not come up with this solution on their own, if you didn't teach them the "accumulator pattern"? For me personally a tutorial with a lot code like that would be interesting. Showing me another version of a recursive descent parser doesn't teach me anything, because I know how to write it (with recursion!!!) in an imperative language...
- chongli 6y ago
  Do you agree that most imperative programmers would not come up with this solution on their own, if you didn't teach them the "accumulator pattern"? Background: I’m currently working as a full time assistant for the first year computer science course at my university. We have around 1800 people enrolled in the class including over 1000 first year CS students. Many of our first years were exposed to imperative programming in high school, either at home or with a high school CS class. The course we teach is based on the book HTDP and uses a purely functional teaching dialect of Racket. Many of our students struggle to figure out how to use the different recursion patterns such as accumulative recursion and mutual recursion. I’m not the GP but I will answer your question anyway: yes, I agree that most imperative programmers would not come up with that solution. I have witnessed it myself first hand. Where I disagree is with any implication or suggestion that they should, given no prior functional programming experience. Accumulative recursion is a standard pattern in functional programming but if you’re an imperative programmer you may not have ever needed to learn it. Therefore, I think it would be unreasonable to expect you to come up with it on the fly.
- a1369209993 6y ago
  > You clearly used a pattern (accumulator) with wich you are familiar. No, I didn't, and please refrain from imputing thought processes without evidence. I didn't even think the word "accumulator" until I got to the last paragraph and needed a term to describe the second argument to w. > Do you agree that most imperative programmers would not come up with this solution on their own If we assume most imperative programmers are idiots as a special case of most people are idiots, sure. I'm not sure that's a good assumption or particularly relevant, though. > Showing me another version of a recursive descent parser doesn't teach me anything Ah, I think I misunderstood your point, then: > > Which problems are hard to solve with recursion instead of iteration? > I found something like splitting a string into words not very intuitive... I assumed you meant that "splitting a string into words" was a example of a problem that was hard to solve with recursion (which I found rather puzzling, because as my example shows, it really isn't), rather than that it wasn't a good/intuitive example to illustrate recursion in the general case (which makes a quite a bit more sense, and I'm afraid I don't have a immediate solution to, sorry).