[Edu-sig] understanding recursion
mpaul at bhusd.k12.ca.us
Tue Feb 20 06:19:25 CET 2007
I'd like to share an idea that occurred to me awhile back.
It's a problem one can pose prior to discussing any specific programming language.
Given two black-box functions prev(n) and next(n), along with conditional reasoning and the typical math comparison operators, define arithmetic.
So for example, visualizing the translation of a segment [a, b] on a number line, we could define difference(a, b) in this way:
if b = 0 ---> a
if b > 0 ---> difference(prev(a), prev(b))
if b < 0 ---> difference(next(a), next(b))
Or, we could make the base case:
if a = b ---> 0
(if a and b are equal, then there is no difference)
and get a slightly different definition.
Understand that this was a pseudo-code style I was using prior to having seen Python. Imagine my joy when I then found Python!
The important thing in these exercises is that we can't use our typical arithmetic operators of +, -, *, /, as we are DEFINING them!
And in the act of defining them, we naturally have to think recursively, as we haven't been given any looping constructs.
I must say - it was Scheme that initially inspired me to think like this.
(That, and the fact that I have frequently found myself without a functional lab at the beginning of the school year! Seriously, it has been unbelievable.)
I think this is a good kind of exercise for both CS and math students.
And this is what made me fall in love with Python right away - the fact that I could do this kind of stuff:
zero = 
def next(n): return [n]
def prev(n): return n
one = next(zero)
two = next(one)
four = next(next(two))
three = prev(four)
In Python, this stuff will RUN!
I was ecstatic for days because of this.
Of course, given this implementation we are restricted to the Naturals - but that's OK. The Naturals is a good place to start! We then have to think about how to implement other kinds of number. I think that constructing this kind of understanding is something we would want kids to do. There could be a lot of history integrated there.
We can also extend the exercise to define > and <. So, given only prev(n), next(n), equality, and conditional reasoning, define arithmetic!
I realize this might seem really remote and abstract for most high school students, but I actually think it's something they COULD and SHOULD grapple with. Exercises like this contain lots of good math AND CS simultaneously.
I mean, consider a high school student who could articulate FROM SCRATCH their understanding of the various kinds of number in a simple computational syntax.
Seems to me that would meet all kinds of concerns regarding standards.
"Shall I tell you what it is to know?
To say you know when you know, and
to say you do not when you do not,
that is knowledge."
More information about the Edu-sig