[Tutor] recursive factoring

[Danny Yoo]

On Thu, 17 Jan 2002 mikalzet@libero.it wrote:

> def fibonacci(n):
>  a = 1L
>  b = 1L
>  if n < 2: return 1
>  else:
> 	z=2
> 	while z <= n:
>  	  c = a + b
>  	  a, b = b, c
>           z = z + n
>         return c
>
> 
> This function seems at least as fast as the previous one, but there is a
> big difference: fibonacci(100000) is possible first go (it takes looong
> seconds and the result is a number of over 20000 digits if I well
> remember).
> 
> This makes me think that perhaps for this sort of chore recursion is
> not as efficient as direct calculation methods.

[warning: this message is sort of a rah! rah! cheerleader message for
Scheme.  *grin*]


Let's do a comparison for a moment.  Here's another recoding of the
fibonacci() function in a recursive style:

###
def fibonacci(n):
    def loop(a, b, x):
        if x == 0: return a
        return loop(b, a+b, x-1)
    return loop(1, 1, n)
###


Before we continue, let's make sure this works.

###
>>> [fibonacci(n) for n in range(10)]
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
###

Ok, that looks right.


Anyway, recursion itself doesn't have to be expensive --- unfortunately,
it's the current implementation of recursion in Python that's not
efficient.  What makes recursion look expensive is the call here:

        return loop(b, a+b, x-1)

and the overhead involved in calling a function.  But let's take a look at
that fragment again:

###
    def loop(a, b, x):
        if x == 0: return a
        return loop(b, a+b, x-1)
###


If Python were "smart", it would realize that all it would need to do to
get equivalent results is to do something like:

###
    def loop(a, b, x):
        while 1:
            if x == 0: return a
            (a, b, x) = (b, a+b, x-1)
###


In language implementations that really support recursion well, this
transformation is done automatically.  The transformation is based on the
following idea: if the very last thing --- the very "tail" of our function
--- is just returning the value of a function, all the system needs to do
is set up our parameters up right, and just goto the function start.  In
CS terms, this is called "tail recursion", and if implemented correctly,
this kind of recursion is just as fast as a while loop.


Unforutnately, Python's standard implementation doesn't do this
optimization.  *sigh* At least, not yet.  (I think the Java implementors
are trying to get it to work in Java now.)


However, it does work with Scheme implementations: if we write fibonacci
in Scheme:

;;;
(define (fibonacci n)
  (define (loop a b x)
    (if (= x 0)  
	a
	(loop b (+ a b) (- x 1))))
  (loop 1 1 n))
;;;

and run it:

;;;
guile> (fibonacci 100000)
4202692702995154386319005101293915131773915702
6322345033047160871983357314572762266339384772
6701366096253366170285832918664116229882221533
3733574147268614522205177960360216576292096795
5306565025379983144950263305006207190888989846
4361959992647623610831850502374986470385949102
4686621241730682736115723551647724257547502352
4124687460748510533539234387035478700197015862
7451490394358177801241082646446182327292482674
9362282954004235923662667858166740323769532233
5408104342666616797388659593046520172457610944
9556607116705430169089571460488401367949139456
6493844646298912078940644595782507997928878739
3929856101801013438826002838203981392009271635
1212296992483983946353362236959988059362454831
...  [lots and lots of digits]
;;;

then this actually runs well, and more importantly, its memory usage is
constant, just as if it were a while loop.


In reality, recursion in Python is not optimal, just because Python
doesn't optimize tail-recursive function calls.  In theory, though,
recursive functions can be just as efficient as functions with loops.

Michael Hudson's "bytecodehacks" package actually does the processing to
make tail-recursion work:

http://bytecodehacks.sourceforge.net/bch-docs/bch/module-bytecodehacks.tailr.html

but, as the name suggests, it's very hacky.  *grin* I think it would take
some extensive thinking to allow tail-recursion to really work in Python.