Re:Real World Haskell
by chongli on Friday November 06, 2020 @05:19PM
(#25011710)
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.
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.