Hacker News Reader

Comment by manish_gill | Hacker News Reader

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?

View on HN

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

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/0...

Hope this helps!

I would say the vast majority of How to Design Programs (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.

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.

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.

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).

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 :)

if Racket was built on top of immutable data structures, recursion, and the likes - why were imperative-like features such as mutation added to the language?

As I haven't used Racket for anything professionally, I can't really answer the question with Racket in mind.

But Clojure is also built on top of immutable data structure, recursion and more, but also provides features for mutation of various things, both for pragmatism and sometimes performance. Clojure also lives like a hosted language (on top of JVM/browser engines/more), most of them being mutable by default, so providing those constructs help with interop as well.

It's not so much that mutation was added to racket. Racket started as a scheme, which has mutation. Some of that, like set-car! and set-cdr! were removed (cons cells were made immutable, though mcons was added for mutable cons cells) set! is one wasn't removed. I think removing set! would constitute a much more radical departure from scheme than what's been done already.

Scheme was defined as an algorithmic language, not a strictly pure-functional one, though it also included some functional features and permitted other functional abstractions to be implemented.

Racket slowly added some immutable data types to Scheme, which was a nice fit for some other Scheme features that had been there from the start, and better for software engineering (e.g., enforce that a user of a module couldn't go and mutate data you were sharing with them).

As a programmable programming language, I think it would be a shame if someone wants to use mutation and it's not available. On the other hand, if you don't want to use it, then don't use it! If you are a language creator that doesn't want your client to use variable mutation, you can even choose to not provide the construct very easily (see the Beginning Student Language which does exactly this).

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-part-b

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! :)

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_Lang...

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

Reply on news.ycombinator.com