Tail Recursive Fibonacci
---- --------- ---------

Preface
-------

The Fibonacci function is directly defined by the
rewrite rules:

    fibonacci ( 0 ) ===> 0
    fibonacci ( 1 ) ===> 1
    fibonacci ( n ) ===> fibonacci ( n - 2 )
			 +
			 fibonacci ( n - 1 )
			    if n >= 2
	where n >= 0 is an integer

A straightforward encoding of these rules as a recursive
function leads to an implementation whose running time
is exponential in the argument n.

There is a well known loop implementation whose running
time is linear in n.

Any loop can be encoded as a `tail-recursive' function.
The rewrite rules to do so for the Fibonacci function
are:

    fibonacci ( 0 ) ===> 0
    fibonacci ( n ) ===> fibonacci_helper ( n, 1, 0, 1 )
			    if n >= 1
	where n >= 0 is an integer

    fibonacci_helper ( n, m, fib_m_minus_1, fib_m )
	===> fib_m	if m == n
	===> fibonacci_helper ( n, m + 1, fib_m,
				fib_m_minus_1 + fib_m )
			otherwise
	where m, n, fib_m_minus_1, and fib_m
	      are integers

Here fib_m is the value of `fibonacci ( m )' and
fib_m_minus_1 is the value of `fibonacci ( m - 1 )'.

You know that fibonacci_helper implements a loop because
in its recursive case it calls itself only as the last
thing it does.  Thus it is said to be `tail-recursive'.

Compilers typically translate tail-recursive functions
into loops in order to save stack space.  Every loop
can be readily written as a tail-recursive function and
every tail-recursive function can be readily translated
into a loop.


Problem
-------

You have been asked to implement the functions fibonacci
and fibonacci_helper according to the tail-recursive
second set of rewrite rules given above.  You are also
asked to print at trace of the execution of these
functions.


Input
-----

The input consists of integers that are to be given as
arguments to the fibonacci function.  There is one
integer per input line.  All these integers are non-
negative.  After the last line containing one of these
integers, there is a line containing the integer -1.
There is no whitespace (SPACEs or TABs) on any input
line.


Output
------

For each input integer you are to call fibonacci ( n ).

Before you call fibonacci ( n ), you are to print a
single blank line.

At the beginning of each of the functions fibonacci and
fibonacci_helper you are to print one line that repre-
sents the call to the function.  This line has the name
of the function, and the arguments as integers separated
by commas inside parentheses.

At the end of each of the functions fibonacci and
fibonacci_helper you are to print one line that repre-
sents the return from the function.  This line has the
name of the function, followed by an equals sign '=',
followed by the result returned by the function.

There must not be any SPACE or TAB characters in any
printed line.  There must not be any sign characters or
leading zeros in the integers printed (zero prints as
`0').  The first line of the output will be blank, and
the last line of the output will NOT be blank.  The
output must be PRECISELY as described.

Notes:
-----

After you add code to the end of the fibonacci and
fibonacci_helper functions to print the return part of
the trace, these functions will no longer be tail-
recursive.

You might wish to experiment further with the idea of
replacing loops by tail-recursive functions by refusing
to use a loop in the main function of your program, and
instead writing that as a tail-recursive function, as in
the pseudo-code:

	main ()
	{
	    read next input
	    if next input >= 0
	    {
		compute next output
		main ()
	    }
	}

Example Input
------- -----

0
1
4
-1


Example Output
------- ------


fibonacci(0)
fibonacci=0

fibonacci(1)
fibonacci_helper(1,1,0,1)
fibonacci_helper=1
fibonacci=1

fibonacci(4)
fibonacci_helper(4,1,0,1)
fibonacci_helper(4,2,1,1)
fibonacci_helper(4,3,1,2)
fibonacci_helper(4,4,2,3)
fibonacci_helper=3
fibonacci_helper=3
fibonacci_helper=3
fibonacci_helper=3
fibonacci=3

Note: the first line of the output is blank and the last
line is NOT blank.




File:	   fibonacci.txt
Author:	   Bob Walton <walton@deas.harvard.edu>
Date:	   Tue Aug 20 11:35:09 EDT 2002

The authors have placed this file in the public domain;
they make no warranty and accept no liability for this
file.

RCS Info (may not be true date or author):

    $Author: hc3 $
    $Date: 2002/08/20 15:34:53 $
    $RCSfile: fibonacci.txt,v $
    $Revision: 1.5 $