# [Edu-sig] understanding recursion

Michel Paul mpaul at bhusd.k12.ca.us
Tue Feb 20 15:54:23 CET 2007

```>why do you say "can't use" we can can just *redefine*

Oh, definitely.  I agree.  We certainly can and SHOULD have students learn to redefine what we mean by various operators.  In saying "can't use" I don't mean "can't EVER use".  : )  I just mean within the scope of this exercise.  Again, I initially meant this to be an exercise PRIOR to studying any particular language.  I think it's a good kind of math/CS exercise to have to analyze what we mean by simple integer operations that we normally take for granted, and this analysis naturally introduces recursion.  And I think it nicely blends in with ultimately redefining these operations for other data structures.

>But in Python, we have been, given looping constructs

Right.  Again, I just mean within the scope of the exercise.

Along this line, here's an interesting thing regarding GCF - suppose we have so far ONLY defined what we mean by greaterThan, lessThan, and difference.  With ONLY those definitions in place, we can define GCF:

gcf(a, b):
if a = b             ---> a
if greaterThan(a, b) ---> gcf(difference(a, b), b)
if lessThan(a, b)    ---> gcf(a, difference(b, a))

We can define gcf prior to defining division or mod.  I think that's kind of interesting.  But certainly, outside the scope of this set of exercises, it makes sense to use looping constructs, and Guido's gcf is pure beauty.

-----Original Message-----
From: kirby urner [mailto:kirby.urner at gmail.com]
Sent: Mon 02/19/07 10:05 PM
To: Michel Paul
Cc: edu-sig at python.org; Jane Wortman; Lee Morris
Subject: Re: [Edu-sig] understanding recursion

> The important thing in these exercises is that we can't use our typical arithmetic > operators of +, -, *, /, as we are DEFINING them!

I think a Pythoneer will twistedly think at this point is:  why do you
say "can't use" we can can just *redefine* __add__, __sub__, other
__ribs__, to suit, get whatever meanings for those typical arithmetic
operators you like.

> And in the act of defining them, we naturally have to think recursively, as we
> haven't been given any looping constructs.

But in Python, we have been, given looping constructs (it's a VHLL ya know,
not an assembly language like Scheme and/or MMIX).

Kirby

```