Re: understanding recursion

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: understanding recursion

John Posner-3
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
Reply | Threaded
Open this post in threaded view
|

Re: understanding recursion

Dethe Elza
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
Reply | Threaded
Open this post in threaded view
|

Re: understanding recursion

kirby urner-4
 
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 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


_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: understanding recursion

John Posner-3
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
Reply | Threaded
Open this post in threaded view
|

Re: understanding recursion

Richard Holbert
Here's another example of recursion:

def is_a_palindrome(t):
    # check to see if t is a palindrome
    if (len(t) >= 2):
        return (t[0] == t[-1]) and is_a_palindrome(t[1:-1])
    else:
        # t is either a single character, or empty string
        return True
_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: understanding recursion

kirby urner-4
In reply to this post by John Posner-3

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
 
Yes I agree that that's fun, about the automatic swapping.
 
Also, it shouldn't escape note that *all* of these recursive
solutions, from elegant to more transparent, seem harder
to grok than the non-recursive version first given, which I
credit to Guido.
 
Kirby
 


_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig