functional programming & tail recursion?
Dennis E. Hamilton
infonuovo at email.com
Tue Feb 29 00:13:38 EST 2000
I am a little puzzled by the discussion on tail recursion. The seems to
imply that tail recursion involves simply catching variations on the case
def f(...):
stuff; ...;
return f(transformed ...)
In my experience, most interesting recursive forms don't automatically take
that structure. And when they do, one might as well go the rest of the way
and implement the recurrence-iteration!
I used the Fibonacci series example previously offered as the basis for my
illustration of tail-recursion solutions in the file fib1.py, below.
The file also demonstrates why one indeed wants to replace recursive
descents by recurrence iterations whenever possible.
Now, what precisely was meant by tail recursion and why is it thought to be
essential to functional programming? What would a tail-recursion
simplification mechanism accomplish given the recursive example, fibn(),
below?
-- Dennis
------------------
Dennis E. Hamilton
InfoNuovo
mailto:infonuovo at email.com
tel. +1-206-779-9430 (gsm)
fax. +1-425-793-0283
http://www.infonuovo.com
- - - - - - - execution with python
1.5.2 - - - - - - - - - - - - - - - - - - -
[1]C:\crea\SoftDev\Python\Projects\PythonTutorial> py fib1.py
Iterative solutions F(-32) to F(+32)
-2178309L 1346269L -832040L 514229L -317811L 196418L -121393L 75025L -46368L
286
57L -17711L 10946L -6765L 4181L -2584L 1597L -987L 610L -377L 233L -144L
89L -55
L 34L -21L 13L -8L 5L -3L 2L -1L 1L 0L 1L 1L 2L 3L 5L 8L 13L 21L 34L 55L 89L
144
L 233L 377L 610L 987L 1597L 2584L 4181L 6765L 10946L 17711L 28657L 46368L
75025L
121393L 196418L 317811L 514229L 832040L 1346269L 2178309L
Tail-recursive F(0) to F(32)
0L 1L 1L 2L 3L 5L 8L 13L 21L 34L 55L 89L 144L 233L 377L 610L 987L 1597L
2584L 41
81L 6765L 10946L 17711L 28657L 46368L 75025L 121393L 196418L 317811L 514229L
832
040L 1346269L 2178309L
Pure-recursive F(0) to F(32)
0L 1L 1L 2L 3L 5L 8L 13L 21L 34L 55L 89L 144L 233L 377L 610L 987L 1597L
2584L 41
81L 6765L 10946L 17711L 28657L 46368L 75025L 121393L 196418L 317811L 514229L
832
040L 1346269L 2178309L
- - - - - - - -
fib1.py - - - - - - - - - - - - - - - - - - - - - - - - - - - -
#! python
"""
Fibonacci-1 Demonstration of Fibonacci Series Generations:
fibn(n) computes F(n) by simple recursion
fibt(n) computes F(n) by tail-recursive form
fibi(n) computes F(n) by explicit iteration
fibz(n) computes F(n) for any integer, Z
dofibs(F, m, n) prints the list of values for F(m) to F(n-1)
"""
# 2000-02-28-20:20 Add little demonstration script for executing
# as application (orcmid)
# 2000-02-28-19:02 Derive all the other flavors, fibn, fibt, and
# fibz, in that order, though I saw fibz right away (orcmid)
# 2000-02-28-16:09 Define fibi iterative solution to demonstrate
# clear equivalence to tail recursion (orcmid)
def fibn(n):
"fibn(n) produces Fibonacci number F(n) by simple recursion"
if n != int(n):
raise "Must be integer"
if n < 0:
raise "Must be non-negative"
if n == 0:
return 0L
if n == 1:
return 1L
return fibn(n-1)+fibn(n-2)
# Simple recursion is a very costly approach to this function.
# Notice that this form is not amenable to improvement by a
# trivial tail recursion. Run dofib(fibn, 2**n) to feel the pain.
def ftail(a, b, i):
"ftail(1L, 0L, n) produces F(n) by tail recursion, n >= 0"
if i == 0:
return b
return ftail(b, a+b, i-1)
def fibt(n):
"fibt(n) produces Fibonacci number F(n) by tail recursion"
if n != int(n):
raise "Must be integer"
if n < 0:
raise "Must be non-negative"
return ftail(1L, 0L, n)
# Function fibt(n) and its auxiliary function ftail(a, b, i)
# provide a tail-recursive form of fibn(n). It is a non-
# trivial exercise to find these automatically with a compiler,
# yet most interesting recursively-defined functions don't
# arrive in an already-tail-recursive form.
# I would like very much to have ftail be local to fibt
# because it depends on preconditions established there.
def fibi(n):
"fibi(n) produces Fibonacci number F(n) by explicit iteration"
if n != int(n):
raise "Must be integer"
if n < 0:
raise "Must be non-negative"
[a, b] = [1L, 0L]
while n > 0:
[a, b, n] = [b, a+b, n-1]
return b
# The explicit iteration form provides all of the economization
# that is gained by establishing tail recursion, in a simple
# well-defined form that is also a clean algorithm.
# I confess that I created fibi(n) first, then used that
# solution as the basis for the fibt-ftail combination.
def fibz(n):
"fibz(n) produces Fibonacci number F(n) for any integer, n"
if n != int(n):
raise "Must be integer"
[a, b] = [1L, 0L]
while n < 0:
[a, b, n] = [b-a, a, n+1]
while n > 0:
[a, b, n] = [b, a+b, n-1]
return b
# Once you see the pattern, it is clear that the Fibonacci
# series is perfectly extendable in both directions from F(0).
# I love the economy of fibz(n) extended to all integers.
# Notice the interesting relationship between F(n) and F(-n).
# This is probably an exercise in the Art of Computer Programming,
# but I am too lazy to verify that.
def dofibs(F, m, n):
"dofibs(F, m, n) prints the sequence F(m) ... F(n-1)"
for i in range(m, n):
print F(i),
if __name__ == "__main__":
# run demonstration test for %python fib1.py
print "\nIterative solutions F(-32) to F(+32)"
dofibs(fibz, -32, 33)
print "\n\nTail-recursive F(0) to F(32)"
dofibs(fibt, 0, 33)
print "\n\nPure-recursive F(0) to F(32)"
dofibs(fibn, 0, 33)
print "\n"
# end of fib1.py
- - - - - - - - end of fib1.py - - - - - - - - - - - - - - - -
-----Original Message-----
From: python-list-admin at python.org
[mailto:python-list-admin at python.org]On Behalf Of Moshe Zadka
Sent: Wednesday, February 23, 2000 23:07
To: Aahz Maruch
Cc: python-list at python.org; python-list at python.org
Subject: Re: functional programming
On 23 Feb 2000, Aahz Maruch wrote:
> >> <blink><blink> What do you call this:
<recursive inefficienct version of fibonacci>
[I said]
> >Um.....the most inefficienct version of fibonacci I've ever seen?
[Aahz]
> Well, sure, but it meets your definition of functional programming. You
> claimed that functional programming is impossible in Python; I've
> provided a counter-example. Do you now retract your claim?
Assuming we're still in "search of truth" mode, rather then "proving I'm
right" mode, I want to clarify my claim: *efficienct* functional
programming is, in general, impossible without tail-recursion. I don't
agree with the timbot that tail-recursion is contrary to the "Python Way",
but it's not in Python right now, anyway.
Are we in agreement now?
--
Moshe Zadka <mzadka at geocities.com>.
INTERNET: Learn what you know.
Share what you don't.
More information about the Python-list
mailing list