[Edu-sig] understanding recursion

[kirby urner]

On 2/20/07, Michel Paul <mpaul at bhusd.k12.ca.us> wrote:

<< snip >>

> 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.

Those moving to the post calculator math class format will likely
register gcf when the discussion advances from N, Z to Q, if that's the
standard (N, Z, Q, R, C is the sequence of number types I'm most
used to teaching, expect to persist, though some might do Q -> Z
and/or combine C with an approach to vectors).[1]

With Q (rational numbers) you get a need for "lowest terms" and
hence for gcfs.  Reduced p/q come as "relatively prime" unless q is 1,
in which case p/q is likewise in Z (int).

So if it's Python we're using, we'll want to construct and/or import
some Rational Number type (not a built-in, unlike in some languages),
with all the methods for adding, multiplying, inverting spelled out in
some detail.[2]

Letting a fraction type accept fractions as inputs (as numerator and
denominator, thence to be simplified), adds the potential for an intriguing
side trip into another deep topic:  continued fractions.[3]

We're also seeding the soup with more mature ideas about the set of
primes versus the set of composites, including that of "uncrackable
composite".

Just because you can't factor (n, m), doesn't mean you can't reduce
n/m to lowest terms, thanks to gcf (Euclid's).  The old grade school
way of doing a gcf, with factor trees and in-common primes, actually
"doesn't scale well" (we have lots of stories at this point, building up
to RSA).[4]

According to this blueprint, students have become familiar with Python's
operator overloading as a part of ordinary algebra, as the "ordinary algebra"
of earlier generations (up to and including the calculator era) has at long
last been superseded with something more useful.[5]

Kirby

[1] combining vector field with C:{(a, b)}
http://www.4dsolutions.net/cgi-bin/py2html.cgi?script=/ocn/python/orbits.py
(next stop:  quaternions?)

[2] some typical Fraction code in Python:
http://www.4dsolutions.net/ocn/python/functions.html

[3]  http://www.cut-the-knot.org/do_you_know/fraction.shtml

[4]  http://www.4dsolutions.net/ocn/rsa.html

[5]  http://www.4dsolutions.net/ocn/cp4e.html