Does anyone have any suggestions?
I think this course will end up to be the start of a revolution in online teaching. We've had MOOCs and OCW, and other courses online for a while now, but this is a whole different level. They enlisted 3Blue1Brown (Grant Sanderson) to lecture. Arguably, he is head and shoulders above everyone else when it comes to mathematical animations and intuitive explanations. Coupling the pedagogical genius of this guy with the research genius of Alan Edelman, and with the expressivity of the new language Julia (which might beat Scheme in the end), this is a recipe for absolute success.
Oh, and the main lectures are live and you can ask questions (and if your question is good, you receive the answer right away).
Run, do not walk, to enlist in this course.
Having discovered programming in a functional language (Ocaml) I found that it was people with prior experience in other languages (such as Python) who had the most trouble getting confortable with recurcion.
I would try it out. It might need some analytically wired thought process, but again that is true for any kind of programming paradigm.
SICP was created to be an introductory computer science textbook back in the day when anybody who actually enrolled in a computer science course could reasonably be expected to be an absolute nerd. It's a book for teaching computer science to people who already have some amount of programming aptitude. It is not a book that tries to teach programming, to hand-hold students through learning practical applications. Yes, it's been shoehorned into many programming courses, but that's not the book's purpose.
HtDP is much better for teaching programming - it's a book that follows many of SICP's ideas, but doesn't presume any relevant experience on the part of the student. It's still not an ideal book for teaching practical programming to a student who doesn't care about any of the CS theory, though.
Whether we look at it as programming or computer science, it's abstract enough that it's highly personal and each person has their own idiosyncratic style of learning.
I did and would benefit much more from a book like SICP than books that are written into a more specific purpose.
It's easy to understand why recursion is useful when you are tasked with traversing a file system. It's not when the first example you are given is calculating Fibonacci sequence.
> One should not conclude from this that tree-recursive processes are useless. When we consider processes that operate on hierarchically structured data rather than numbers, we will find that tree recursion is a natural and powerful tool. But even in numerical operations, tree-recursive processes can be useful in helping us to understand and design programs. For instance, although the first fib procedure is much less efficient than the second one, it is more straightforward, being little more than a translation into Lisp of the definition of the Fibonacci sequence. To formulate the iterative algorithm required noticing that the computation could be recast as an iteration with three state variables.
Hopefully a professor in a course would make similar statements (I know mine did, repeatedly). And, at least in my early programming courses, we quickly (within a week or two) went on to those other problems where recursion was a natural and useful solution. The professors  introduced problems where recursion was either necessary (using for/while loops would be a non-trivial transformation with no performance gain) or, like naive Fibonacci, natural expressions of the problem.
 I transferred universities, not all courses lined up so I got to see the second school's introduction to this topic even though I was past that point academically. I was an unpaid TA (technically I guess I was paying to be the TA).
The very first exercise should be as simple as possible. Explicitly because you're introducing a new concept and so want as little else in the way as you can arrange.
However, the Fibonacci sequence provides good end to end example of recursion, then tail recursion/dynamic programming.
Recursion is hard for students to grasp when taught in math contexts as well, so I don't think this is a matter of prior CS teaching biasing them one way.
This can be interpreted two ways:
1. It really is an introductory text and, as the book says, recursion is a simple, powerful, familiar idea.
2. Times have changed.
I’m partial to interpretation #1
Another good easy to learn as a first language in my experience is Rebol because it allows you to do stuff you ( meaning a person who uses a computer) might want to do quickly (send emails, scrape websites)
Of course another benefit of SICP is that it is written by people who are probably better writers about languages than most of the programmers hired to write programming books and articles.
I'm not disagreeing with you as I write this, more pontificating on teaching styles... we all know recursion can get tricky / be hard to understand in the context of a programming language, but sometimes it's all in the presentation... if we tell the student right up front "hey, this is how we do this, no big deal right?" then perhaps they don't put up their natural defenses and make it into a harder concept than it really is?
This book looks good but I don't think I should start reading it, because I get the feeling it's going to let me want to create my own "powerful programming language" and be led down that (long, probably dark) rabbit hole.