[Edu-sig] More Lesson Planning (correction)

[Tim Peters]

[Kirby Urner]
>> [2] I notice the Scheme books do a 'tail-recursive'
>>    version of factorial that doesn't require two
>>               ^^^^^^^^^

> Correction:  this should have been 'fibonacci', not
> factorial.  Like, in Python I might write:
>
> def fibbo(n):
>     # return nth fibonacci number
>     if n == 0: return 0
>     elif n == 1: return 1
>     else: return fibbo(n-1) + fibbo(n-2)
>
> but that sets up two separate recursive calls.  There's
> a "tail recursive" alternative which sets up an inner
> function accepting two args that I saw in a Scheme
> text.  Wondering if there's a Python equivalent.
> Can internal defs be recursive, is the first question?
> Yes, I tried.  But I'm no Python guru.

There's a Python equivalent for everything <0.7 wink>, but "writing Scheme
in Python" is a bad road to go down.  Tail recursion is vital in Scheme but
of no particular interest in Python (the Python interpreter doesn't look for
it -- it does you no good (that's true in most languages, btw) -- in Scheme
it can make the difference between a program that works and one that "blows
up" the stack).

Similarly, there are (exceedingly non-obvious!) ways to do nested recursive
functions in Python, but they're unnatural in Python too:  the scoping rules
highly discourage it.  "Flat is better than nested" is a good rule of thumb
in Python.  The things Scheme does with lexical closures are intended to be
done with objects and explicit state in Python; in small examples the point
to that is admittedly hard to get across; but read a Scheme function nested
ten levels deep and it's hard to miss <wink>.

An iterative Fibonacci function is most natural in Python.  The one above is
very inefficient (in Python or Scheme).  BTW, note that the function
recurses infinitely if an integer < 0 is passed.  Python will detect that
and raise an exception (although in 1.5.2, the detection doesn't work in the
Windows release; fixed long ago, but not yet released); a tail-recursive
Scheme program that gets into an infinite loop just runs forever.

Interesting in *both* Python & Scheme (= *all* languages with recursion) is
a technique called "memoization" for speeding functions like this, and
that's interesting from both the "comp sci" and "practical programming"
points of view.  Like so, where I've taken the liberty of repairing the
infinite-loop bug too (and where from all points of view, the value of
validating arguments cannot be overemphasized):

_fibcache = {}

def fib(n):
    if n < 0:
        raise ValueError("fib argument must be >= 0: " + str(n))
    elif _fibcache.has_key(n):
        return _fibcache[n]
    elif n <= 1:
        result = long(n)    # prevent overflow
    else:
        result = fib(n-1) + fib(n-2)
    _fibcache[n] = result
    return result

Then test:

>>> fib(5000)  # takes a noticeable (but small) amount of time
38789684543883256337019163083259053120821277146462451061605972148
95550139044037097010822916462210669479293452858882973813483102008
95498294036143015691147893836421656394410691021450563413370655865
62382546567007125259299038549338139288363783475189087629707120333
37052923107693008518093849801803847813996748881765554653788291644
26891298038461377896902150229308247566634622492307188332480328037
50391303529033045058427011476352422702109346376991040067141748832
98422891491273104054328753298044273676822977244987749874555691907
70388063704683279481135897373999311010621930814901857081539785437
91953056175107610530756887837660336673554452588448862416192105534
57493675897849027988234351023599844663934853256411952221859563060
47536464547076033090242080638258492915645287629157575914234380914
23029174910889841552098544324865940797935713168416928680395453095
45388698114665082066862897420639323438488465240988742395873801976
99382031717420893226546887936400263079778005875912967138963421425
25791168727556003603113705477547246046399875880469851784086743828
63125L
>>> fib(5000)  # doing it again appears instantaneous
38789684543883256337019163083259053120821277146462451061605972148
95550139044037097010822916462210669479293452858882973813483102008
95498294036143015691147893836421656394410691021450563413370655865
62382546567007125259299038549338139288363783475189087629707120333
37052923107693008518093849801803847813996748881765554653788291644
26891298038461377896902150229308247566634622492307188332480328037
50391303529033045058427011476352422702109346376991040067141748832
98422891491273104054328753298044273676822977244987749874555691907
70388063704683279481135897373999311010621930814901857081539785437
91953056175107610530756887837660336673554452588448862416192105534
57493675897849027988234351023599844663934853256411952221859563060
47536464547076033090242080638258492915645287629157575914234380914
23029174910889841552098544324865940797935713168416928680395453095
45388698114665082066862897420639323438488465240988742395873801976
99382031717420893226546887936400263079778005875912967138963421425
25791168727556003603113705477547246046399875880469851784086743828
63125L
>>> fib(1)
1L
>>> fib(-1)
Traceback (innermost last):
  File "<pyshell#12>", line 1, in ?
    fib(-1)
  File "D:/Python/misc/fib.py", line 5, in fib
    raise ValueError("fib argument must be >= 0: " + str(n))
ValueError: fib argument must be >= 0: -1
>>>

In Scheme, the cache is most naturally set up via a lexical closure.  Making
it a module vrbl in Python has a real advantage, in that it's trivial to
inspect the contents whenever you like (& Scheme can also do it this way,
although it's kinda "impure" in that worldview and so will earn you raised
eyebrows and muted clucking <wink>):

>>> _fibcache  # empty at first
{}
>>> fib(3)
2L
>>> _fibcache  # see what's in it now
{3: 2L, 2: 1L, 1: 1L, 0: 0L}
>>> fib(20)
6765L
>>> _fibcache  # detecting a pattern yet?
{20: 6765L, 19: 4181L, 18: 2584L, 17: 1597L, 16: 987L, 15: 610L,
 14: 377L, 13: 233L, 12: 144L, 11: 89L, 10: 55L, 9: 34L, 8: 21L,
 7: 13L, 6: 8L, 5: 5L, 4: 3L, 3: 2L, 2: 1L, 1: 1L, 0: 0L}
>>>

Note that IDLE and PythonWin have good facilities for replaying earlier
lines, and for word-completion, so I only had to type "_fibcache" once.
Prettier output can be gotten via using the pprint (for "pretty print")
module:

>>> import pprint
>>> dir(pprint)  # see what's in it (refreshing my memory)
['DictType', 'ListType', 'PrettyPrinter', 'StringIO', 'TupleType',
 '_Recursion', '__builtins__', '__doc__', '__file__', '__name__',
 '_safe_repr', 'isreadable', 'isrecursive', 'pformat', 'pprint',
 'saferepr']
>>> print pprint.pprint.__doc__  # was pprint it?
Pretty-print a Python object to a stream [default is sys.sydout].

>>> pprint.pprint(_fibcache)  # yup, that was it
{0: 0L,
 1: 1L,
 2: 1L,
 3: 2L,
 4: 3L,
 5: 5L,
 6: 8L,
 7: 13L,
 8: 21L,
 9: 34L,
 10: 55L,
 11: 89L,
 12: 144L,
 13: 233L,
 14: 377L,
 15: 610L,
 16: 987L,
 17: 1597L,
 18: 2584L,
 19: 4181L,
 20: 6765L}
>>>

There's been some thought given to letting you "hook" the interpreter's
"automagic output" formatting function, so that e.g. pprint could be invoked
"by magic" all the time (or any function to do any kind of processing you
like).

The "jog my memory" and "print the help" procedures above are (IMO) too
clumsy right now.

not-the-answer-you-asked-for-but-hope-it-was-interesting-
    anyway<wink>-ly y'rs  - tim