[Edu-sig] understanding recursion

[Michel Paul]

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

==================================================