[Edu-sig] understanding recursion
Michel Paul
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:
difference(a, b):
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[0]
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.
Sincerely,
Michel Paul
==================================================
"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."
- Confucius
==================================================
More information about the Edu-sig
mailing list