Menu
I've been bouncing around functional languages for the last few months from F# to Haskell to Scheme (Racket). I've never really used recursion much, but Haskell and its pattern matching really helped me to be less afraid of them. Now that I'm using Scheme, I seem to default to recursive methods. I'm curious if this is indicative of just going through an "ooo shiny!" phase or if recursion is a staple of Scheme development.
Side note: I've been shooting for tail recursion whenever I write recursive methods.
311
Tail recursion has special status in Racket because the compiler notices tail calls and optimizes them. Ordinarily, each call to a function, including a recursive call, causes another set of arguments to be saved in a block of memory called the call stack.
Thus, recursion may cause memory overflow if your stack space is large, and is also inefficient in cases where the same value is calculated again and again. So, use either iteration or recursion according to the task you want to perform.
A recursive function always has to say when to stop repeating itself. There should always be two parts to a recursive function: the recursive case and the base case. The recursive case is when the function calls itself. The base case is when the function stops calling itself.
Recursion is made for solving problems that can be broken down into smaller, repetitive problems. It is especially good for working on things that have many possible branches and are too complex for an iterative approach . One good example of this would be searching through a file system.
I think it depends what type of recursion you're talking about.
The first eye-opener (for instance if you're working through SICP) is that iteration can be replaced by recursion. All those lines of tedious and error-prone loop code you've written in a past life, can be done another way. This is a cool and (as you put it) "ooh shiny!" experience.
The next eye-opener is how little of that sort of recursive code you'll actually write in real life. Instead, you'll avoid tedious iteration -- and tedious recursion, both -- by using building blocks like map and fold.
Furthermore in Racket you'll probably graduate from map and fold to preferring the "comprehensions" like for/list, for/vector, and for/fold that work on sequences not just lists. Up the food chain you keep going.
Having said that, there are some problems you will best solve recursively (not just "iteration by other means"). And the comfort level you got in eye-opener number one, will help there, I think.
116
No, it's not a phase, it is a staple. Recursion is a technique that allows you to solve more complex problems than you otherwise would be able to tackle easily—and even in cases where you want an iterative solution, it's easier to arrive at that if you first formulate a recursive one.
Mastering recursion also opens up new problem areas to you. Typical iterative-only programmers are not equipped to deal with problems that, for example, involve manipulating and translating between formal languages like, e.g., writing complex SQL query generators on the basis of an encoded description of the report the user wants to see.
If you want to move forward, you should look into getting more comfortable with folds, which abstract away from explicit recursion by separating the recursive structure of a computation from the content of the recursive steps. So for example Scheme's fold-right can be seen as "perform a recursive computation that has the same shape as this list, mapping the empty list to this value as the base case, and each cons to this function." Then there's folds on other, more complex data structures.
44
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
