# Re: understanding recursion

6 messages
Open this post in threaded view
|

## Re: understanding recursion

 Andy Judkis <[hidden email]> wrote: > ... I've found that many kids seem to have a natural ability > to use recursion, but they don't realize that they're doing it, and > they don't understand the implications. > >   ... > > def play_game(): >     . . . >     resp = raw_input("Play again?") >     if resp == "yes": >         play_game() > My guess, Andy, is that many of the students are not thinking clearly enough to understand the difference between REPETITION and RECURSION. They haven't thoroughly learned the flow-of-control aspect of functions/subroutines. That's not surprising: in real life, kids don't have to formally declare one activity to be finished before they "go to" (heh heh) another activity. IMHO, the kids' first attempt at coding provides an excellent opportunity for you to gently move them from the realm of almost-right "fuzzy" thinking to "crisp" formal algorithmic thinking. > ...  My expectation was that they'd write a loop like this: > > while True: >     play_game() >     resp = raw_input("Play again?") >     if resp == "no": >         break > Another guess: not many kids will hit upon the "while True ... break" coding scheme on their own. I'd be inclined to let them use this imperfect solution at first:   for i in range(1000000):        play_game()        ... Then you can point out the limitations, inefficiencies, lack of elegance of this solution -- e.g. to quit the game, you have to type Ctrl-C or close the window. Best, John _______________________________________________ Edu-sig mailing list [hidden email] http://mail.python.org/mailman/listinfo/edu-sig
Open this post in threaded view
|

## Re: understanding recursion

 Here's my 0.02.  Take with a grain of salt, I've been feverish with   the flu the last couple of days When the issue comes up, why not step away from the computers and   simply draw a stack on the whiteboard?  Show how looping stays at the   same place in the stack and recursion will eventually overflow the   stack. They don't have to understand all the details of why (or why   recursion doesn't have that effect in all languages), but a simple   picture should give them enough to know why to avoid one over the other. --Dethe "The Brazilian government is definitely pro-law. But if law doesn't   fit reality anymore, law has to be changed. That's not a new thing.   That's civilisation as usual." --Gilberto Gil, Brazilian Minister of   Culture _______________________________________________ Edu-sig mailing list [hidden email] http://mail.python.org/mailman/listinfo/edu-sig
Open this post in threaded view
|

## Re: understanding recursion

 A recent thread on recursion math-thinking-l might be of interest.   Many pro computer scientists like to teach about it in tandem with Peano Arithmetic (PA) i.e. mathematical induction.   Of course if the students are already math phobic...    But the idea here is a CS approach gives you a second chance to get turned on by what turned you off the first time, i.e. those traditional [I'd say antiquated] high school math classes wherein computer languages are strictly forbidden and/or sidelined without comment.   Hope yr feelin' better Dethe.  Having the flu sucks.   Kirby   On 2/9/07, Dethe Elza <[hidden email]> wrote: Here's my 0.02.  Take with a grain of salt, I've been feverish withthe flu the last couple of days When the issue comes up, why not step away from the computers andsimply draw a stack on the whiteboard?  Show how looping stays at thesame place in the stack and recursion will eventually overflow thestack. They don't have to understand all the details of why (or why recursion doesn't have that effect in all languages), but a simplepicture should give them enough to know why to avoid one over the other.--Dethe"The Brazilian government is definitely pro-law. But if law doesn't fit reality anymore, law has to be changed. That's not a new thing.That's civilisation as usual." --Gilberto Gil, Brazilian Minister ofCulture_______________________________________________ Edu-sig mailing list[hidden email]http://mail.python.org/mailman/listinfo/edu-sig _______________________________________________ Edu-sig mailing list [hidden email] http://mail.python.org/mailman/listinfo/edu-sig
Open this post in threaded view
|

## Re: understanding recursion

 In reply to this post by John Posner-3 Kirby offered Euclid's Algorithm as an example of a recursive function: > def gcd(a,b): >    if b: >       return gcd(b, a % b) >    return a This example *is* wondrous for demonstrating recursion, because it's so elegant and terse. But IMHO, these qualities make it less than ideal for *teaching* recursion. In particular, the terminal case is implied instead of defined: "if b == 0, then return a as the GCD of the original numbers". Here's an implementation that makes more pedagogical sense to me: def gcd(x,y):     # terminal case:     # smaller goes into larger evenly, or     # smaller has been whittled down to 1     if x % y == 0 or y == 1:         return y     # recursive case:     # smaller does not goes into larger evenly     # GCD must go into the _remainder_ evenly     else:         return gcd(y, x % y) Sure, including the "y == 1" case as a separate test might be overdoing it a bit (but it does eliminate one recursion). Another problem (both with Kirby's implementation and mine) is that you "get lucky": if the user specifies the smaller number and the larger number in the "wrong" order, the algorithm magically swaps them for the next recursion. When tackling other recursion problems, students probably won't be able to count on such luck. -John _______________________________________________ Edu-sig mailing list [hidden email] http://mail.python.org/mailman/listinfo/edu-sig