5 ms·

I've picked up Racket recently after a long while and I'm enjoying it. Does anyone have recommendations of how to learn to think recursively? Sure, using the l

I've picked up Racket recently after a long while and I'm enjoying it. Does anyone have recommendations of how to learn to think recursively? Sure, using the language more and more does it, but what about a more general recursion as a problem solving paradigm pattern? I'm enjoying doing recursive code exercises and got into Backtracking problems. Creating things like Sudoku solvers, Knight's Tour grid etc was quite fun. I still can't develop recurrences easily though. Any books/exercises that people here found helpful?

doneata 6y ago
This paper, "Programming by Numbers: A Programming Method for Novices", presents a recipe of how to design recursive functions: https://eprints.soton.ac.uk/254242/1/p_by_numbers.pdf https://eprints.soton.ac.uk/254242/1/p_by_numbers.pdf And the "The Little Schemer" book has a series of exercises that expose recursive thinking: https://www.amazon.com/Little-Schemer-Daniel-P-Friedman/dp/0262560992 https://www.amazon.com/Little-Schemer-Daniel-P-Friedman/dp/0... Hope this helps!
skrishnamurthi 6y ago
I would say the vast majority of How to Design Programs (https://htdp.org/ https://htdp.org/) is about exactly this. It's not presented this way, but that's what the Design Recipe makes you really good at.
bgorman 6y ago
The little schemer is a book purpose built to teach this.
emmanueloga_ 6y ago
I like EOPL 3rd edition, the first two chapters are pretty much dedicated to explaining recursion [1]. 1: https://en.wikipedia.org/wiki/Essentials_of_Programming_Languages https://en.wikipedia.org/wiki/Essentials_of_Programming_Lang...
nikofeyn 6y ago
as others have said, the little schemer (for functions) and also the little mler (for types) are purpose built to thinking about functions and types recursively. also, the coursera course programming languages by dan grossman is an excellent course on doing things recursively. in part a, you learn sml, and in part b, you learn racket and build a simple interpreter. https://www.coursera.org/learn/programming-languages https://www.coursera.org/learn/programming-languages https://www.coursera.org/learn/programming-languages-part-b https://www.coursera.org/learn/programming-languages-part-b
- manish_gill 6y ago
  I actually finished that course when it first came out (and was a single course as opposed to a 3 part breakdown) way back, like 4-5 years ago. Thanks all for the suggestions! :)
neilv 6y ago
One way to learn some of using recursion while using Racket (or any other Scheme) is to: * avoid the iteration constructs that Racket added to Scheme, * avoid mutating operations, such as `set!` and those that operate on mutable data types, * embrace named-`let` for iteration/recursion (using `let` with a name, like `(let loop-for-foo (` rather than `(let (`, which effectively makes it like an embedded function that can be called from within its own definition), and * embrace immutable data for collections, like immutable pairs and immutable hashes. You can do that for real-world development, or for interview-oriented Leetcode-type exercises. Whichever motivates one more; with the above suggestions, both will present many opportunities to practice recursion this way, without exercises that are selected or contrived to need recursion.
- bjoli 6y ago
  I agree, but regarding the for constructs, I don't think many people know: Racket's for loops are just (mostly) left folds over whatever sequences you use. They become as efficient as hand-rolled named lets.
  - neilv 6y ago
    And then people don't get comfortable with recursion, and when they have an algorithm that doesn't quite fit a `for` exactly, they do things like mutate a flag variable. :) I think that situation is unfortunate for some aspects of learning, whether or not the compiler can make some use cases of the constract just as fast (or faster).
    - bjoli 6y ago
      I agree! I solved it by implementing mostly-racket-compatible for loops for guile scheme. Since then I can't not think of for loops as recursive macros :) Edit: the loops actually got more powerful recently: The for/foldr was a great addition where you can replace most non-tail-recursive functions with it, even though I probably wouldn't use it for tree transversal :)
- ausbah 6y ago

doneata 6y ago

This paper, "Programming by Numbers: A Programming Method for Novices", presents a recipe of how to design recursive functions: https://eprints.soton.ac.uk/254242/1/p_by_numbers.pdf https://eprints.soton.ac.uk/254242/1/p_by_numbers.pdf And the "The Little Schemer" book has a series of exercises that expose recursive thinking: https://www.amazon.com/Little-Schemer-Daniel-P-Friedman/dp/0262560992 https://www.amazon.com/Little-Schemer-Daniel-P-Friedman/dp/0... Hope this helps!

skrishnamurthi 6y ago

I would say the vast majority of How to Design Programs (https://htdp.org/ https://htdp.org/) is about exactly this. It's not presented this way, but that's what the Design Recipe makes you really good at.

bgorman 6y ago

The little schemer is a book purpose built to teach this.

emmanueloga_ 6y ago

I like EOPL 3rd edition, the first two chapters are pretty much dedicated to explaining recursion [1]. 1: https://en.wikipedia.org/wiki/Essentials_of_Programming_Languages https://en.wikipedia.org/wiki/Essentials_of_Programming_Lang...

nikofeyn 6y ago

as others have said, the little schemer (for functions) and also the little mler (for types) are purpose built to thinking about functions and types recursively. also, the coursera course programming languages by dan grossman is an excellent course on doing things recursively. in part a, you learn sml, and in part b, you learn racket and build a simple interpreter. https://www.coursera.org/learn/programming-languages https://www.coursera.org/learn/programming-languages https://www.coursera.org/learn/programming-languages-part-b https://www.coursera.org/learn/programming-languages-part-b

manish_gill 6y ago
I actually finished that course when it first came out (and was a single course as opposed to a 3 part breakdown) way back, like 4-5 years ago. Thanks all for the suggestions! :)

neilv 6y ago

One way to learn some of using recursion while using Racket (or any other Scheme) is to: * avoid the iteration constructs that Racket added to Scheme, * avoid mutating operations, such as `set!` and those that operate on mutable data types, * embrace named-`let` for iteration/recursion (using `let` with a name, like `(let loop-for-foo (` rather than `(let (`, which effectively makes it like an embedded function that can be called from within its own definition), and * embrace immutable data for collections, like immutable pairs and immutable hashes. You can do that for real-world development, or for interview-oriented Leetcode-type exercises. Whichever motivates one more; with the above suggestions, both will present many opportunities to practice recursion this way, without exercises that are selected or contrived to need recursion.

bjoli 6y ago
I agree, but regarding the for constructs, I don't think many people know: Racket's for loops are just (mostly) left folds over whatever sequences you use. They become as efficient as hand-rolled named lets.
- neilv 6y ago
  And then people don't get comfortable with recursion, and when they have an algorithm that doesn't quite fit a `for` exactly, they do things like mutate a flag variable. :) I think that situation is unfortunate for some aspects of learning, whether or not the compiler can make some use cases of the constract just as fast (or faster).
  - bjoli 6y ago
    I agree! I solved it by implementing mostly-racket-compatible for loops for guile scheme. Since then I can't not think of for loops as recursive macros :) Edit: the loops actually got more powerful recently: The for/foldr was a great addition where you can replace most non-tail-recursive functions with it, even though I probably wouldn't use it for tree transversal :)
ausbah 6y ago