Re: Recursion
EECS Instructional Account
> 2) Maybe I'm reading this as more of a "why?" than a "how?" question, but I
> typically _don't_ use it to solve problems because of the issues with stack
> overflows, difficulty in debugging, etc. Since most (and I'm betting it has
> been proved that _all_) problems that can be solved by recursion can be
> rewritten using conditional loops, it rarely occurs to me to use recursion to
> solve a particular problem.
>
Yeah, I was thinking more of a "how" question, but you raise an
interesting point.
First, the issue of stack overflow. In the section we skipped (1.2) it
talks about writing iterative loops with recursion. This puts loops as
a special case of recursion, and the scheme interpreter is smart about
recognizing such loops and reusing stack space to run the loop, and it
won't cause stack overflow.
For more complicated recursive procedures, the iterative versions would
end up using the same amount of space, the only difference being that
one version uses space in the heap instead of the stack (so the recursive
version may cause stack overflow when the other doesn't). But the
difference would only be noticed on fairly large input.
(AH! I just realized that there /is/ a way to avoid stack overflow if you
write your interpreter/compiler cleverly enough...)
But anyway, the point of this course is not about such details (stack,
memory),
it is about thinking and programming in terms of the structure of a
problem rather than in terms of how the computer works. And in this sense,
recursion is a powerful way of thinking about problems, even more so when
we look at more complicated structures such as trees.
As for the second point about debugging, it probably depends. But in this
particular course, the tasks are much easier to get right with
recursion rather than iteration. Most of the exercises/examples we will
see in this course have a naturally recursive structure (this is partly due
to the use of the Scheme in some cases)
EECS Instructional Account
For the first one, I thought it fitting to bring up an explanation of
recursion (or rather, how computers work) from Brian Harvey's lecture. I
hope I can capture all the details.
So anyway... the secret to computers is that inside your computer there
are
millions of little people. And each little person is a specialist in doing
some task (a procedure). So in the example from lecture...
(define (argue sent)
(if (empty? sent) '()
(se (opposite (first sent))
(argue (bf sent)))))
There are millions of little people that are specialists in how to "argue"
on a sentence, there are millions of little people that are specialists in
how to "empty?" (check if a sentence is empty), there are "sentence"
specialists, "opposite" specialists, etc...
And so, for something as simple as
(argue '(i like cheese))
Scheme gives the sentence (i like cheese) to an argue specialist, say
Arnold. And he follows his cheat sheet (the procedure body), first
giving the sentence to a specialist in "empty?" (say Evan). Evan
says "no, it's not empty", which prompts Arnold to give
this sentence to a specialist in "first" (say Fred). Fred does his job
and gives Arnold "i" back. Arnold then gives "i" to an "opposite"
specialist, who gives Arnold back "i".
After consulting the "butfirst" specialist to get (like cheese), he needs
an "argue" specialist.
He then consults another "argue" specialist (say
Alice), and gives her (like cheese). Then he waits for her to do her task.
What does Alice do? Like Arnold, she consults specialists to split the
sentence and do the opposite to get "hate" and (cheese). She then gives
(cheese) to another "argue" specialist, Albert.
Albert does the same thing as Alice, splits the sentence into "cheese"
and (), gives () to another "argue" specialist Alan.
Alan sees (), and (wow what an easy task) gives () back to Albert.
Albert takes the result and (remember there's more to do) consults a
"sentence" specialist to combine "cheese" and () into (cheese). He hands
this to Alice.
Alice consults a "sentence" specialist to combine "hate" and (cheese) to
get (hate cheese). She passes this to Arnold.
Arnold does the same thing to get (i hate cheese). And finally the little
people have finished the task.
That's the story of the little people who work so hard inside your
computers.
What does this mean for writing recursive procedures? Well, I suppose a
trick would be to reverse-engineer this process to figure out how to get
them to do what you want.
On Tue, 24 Jun 2008, Evan Chou wrote:
> To encourage discussion on the newsgroup, let me throw something out there.
>
> How do you think about Recursion? There are two parts to this.
>
> 1. How does it work?
> 2. How do you use it to solve problems?
>
> It would be nice to know how you think, because actually, this is one of the
> hardest concepts to explain well (and completely). It's easy if you have a
> mathematical background in induction, but that's cheating (and most people will
> not have seen that until cs70/math55)
>
EECS Instructional Account
Nope, I think it was very interesting. I hope by the end of this course
you can appreciate the power of recursion (although as you say, in
practice I think it tends to be avoided).
(I also didn't want to sound like "recursion is the only way to do
things". Just wanted to express that "recursion is beautiful")
Hopefully the language barrier will be overcome soon for most people. Of
course, I do prefer that the problems people are having are syntax-related
rather than thinking-recursion-related.
On Thu, 26 Jun 2008, Glenn Edward Sugden wrote:
> Wow, fast reply.
>
> I hope that my comments didn't sound too judgemental - it was quickly clear
> that this would be more of a course about the process of solving a programming
> problem rather than just banging out some optimal solution... especially
> considering the fact that we are using Scheme instead of [insert language of
> the month here].
>
> I'm also in that frustrated phase of knowing how to shortcut straight to a
> solution, rather than thinking about ways to solve a problem, and feeling like
> the language is "just getting in my way."
>
> I'm sure there's a method to the madness... I just have to keep plugging away
> until I can see/use it as a tool rather than a challenge... let's just hope I
> have enough plasticity left...
>
Evan Chou
didn't have my name up there.. oops. I just added it into pine settings.
I haven't "drunk the FP koolaid" myself.. but it seems very interesting.
(I tried to learn Haskell at one point and gave up, but that might be
because I was reading the tutorial without actually trying things out.
That and time) Even then, I think it's useful to have many different
ways to think about a problem.
Nothing wrong with wanting to be a computer science teacher, I think.
Sounds like a rewarding job :)
On Fri, 27 Jun 2008, Glenn Sugden wrote:
> In article <g413dk$1c2h$1...@agate.berkeley.edu>, cs61...@imail.EECS.Berkeley.EDU
> (Class Account) writes:
>
> [snip "sane" perspective]
>
> I appreciate your reply... it's definitely helpful to to look at it as a
> fresh start instead of tear-it-all-down-and-rebuild-it-differently sort of way.
>
>> Just drink the FP kool-aid and you'll be leet
>
> (aim face) (open valve fire-hose)
>
>> and working for google in no time...
>
> ...and here's the really twisted part. I (recently) passed up an offer to
> work at Google in their AI group to become a ... wait for it ... computer
> science teacher.
>
> Stop rolling your eyes and shaking your head. I can see you. Stop that.
>