// Assignment 4 Functions for CS 51 Introduction to C
//
// File:	asst4.cc
// Author: 	<your name> (<your e-mail address>)
// Assignment:	c

// This file contains the assigment 4 functions for
// programming in the C subset of C++.

#include <stdlib.h>

// RR: fibonacci (m) ===> m	if m <= 1
//     fibonacci (m) ===>   fibonacci ( m - 2 )
//			  + fibonacci ( m - 1 )
//				if m > 2
//     where m is an integer

int fibonacci ( int m )
{
    return 0; // Replace this line with your C code.
}

// Cache interface:
//
// RR: cached (m) ===> n if cache (m, n) was executed
//			 previously and 0 <= m < 100
//                ===> -1 otherwise
//
//     cache (m, n) ===> n and caches the pair (m, n)
//			  as a side effect
//			  if 0 <= m < 100
//
//     where m, n are an integers

int * cache_data = NULL;

int cached ( int m )
{
    return -1;  // Replace this line with your code. 
}

int cache ( int m, int n )
{
    if ( cache_data == NULL )
    {
	int * p    = new int [100];
	int * endp = p + 100;

	cache_data = p;

	while ( p < endp ) * p ++ = -1;
    }

    if ( 0 <= m && m < 100 )
        cache_data [m] = n;

    return n;
}

// Memoizing Fibonacci:
//
// RR: memo_fibonacci (m) ===> m    if m <= 1
//     memo_fibonacci (m) ===> cached (m)
//				    if m > 2 and
//				       cached (m) != -1
//     memo_fibonacci (m) ===>
//	   cache (m, memo_fibonacci ( m - 2 )
//	             + memo_fibonacci ( m - 1 ))
//				if none of above apply
//     where m is an integer

int memo_fibonacci ( int m )
{
    return 0;  // Replace this line with your code. 
}

// Tail Recursive Fibonacci function

// Recursion Variables:
//
//   fibonacci_recurse ( m, n, fn_previous, fn )
//
//      m	The value for which the fibonnaci
//		function is to be computed.
//
//	n	The last value for which the fibonnaci
//		function has been computed so far.
//
//	fn_previous	Equals fibonacci ( n - 1 )
//
//	fn		Equals fibonacci ( n )


// RR: tail_fibonacci ( 0 ) ===> 0
//     tail_fibonacci ( m )
//	   ===> fibonacci_recurse ( m, 1, 0, 1 )
//
//     fibonacci_recurse ( m, n, fn_previous, fn )
//	   ===> fn if m == n
//	   ===> fibonacci_recurse
//		    ( m, n+1, fn, fn_previous + fn )
//				if m != n
//
//     where m, n, fn_previous, fn are an integers

int tail_fibonacci ( int m )
{
    return 0;  // Replace this line with your code. 
}