fibmemo.c

/*
 * Recursive Fibonacci program, with memos
 *
 * Matt Bishop, ECS 36A
 *
 * -- May 21, 2024	Original program
 */
#include <stdio.h>
#include <stdlib.h>

/*
 * Globals -- we need these preserved across recursive
 * calls
 */
int *pastfib;		/* (allocated) array of previously computed numbers */
int topfib;		/* 1 beyond index of last number stored */

/*
 * initialize -- create array for computed Fibonacci numbers
 *
 * n = how many Fibonacci numbers to compute
 * we need this to know how big to make the array
 */
void init(int n)
{
	int *p;		/* pointer to allocated space */

	/* allocate the space, quit on error */
	if ((p = (int *) malloc(n * sizeof(int))) == NULL){
		perror("memo: malloc");
		exit(EXIT_FAILURE);
	}

	/* now set up the array and top index */
	pastfib = p;
	topfib = 0;
}

/*
 * release allocated space
 */
void clear(void)
{
	/* you expected maybe system calls or assembly language? */
	(void) free(pastfib);
	pastfib = NULL;
}

/*
 * the interior, recursive function
 * called by fib, which does error checking
 */
int fibx(int n)
{

	/* if we've computed it already, return it */
	if (n < topfib)
		return(pastfib[n-1]);
	
	/* no, we need to compute it */
	/* BASE CASE: n = 1 or 2, fibonacci number is 1 */
	/* make sure we add it to the array!            */
	if (n == 1){
		pastfib[topfib++] = 1;
		return(1);
	}

	if (n == 2){
		pastfib[topfib++] = 1;
		pastfib[topfib++] = 1;
		return(1);
	}

	/* recurse, and note you just added something */
	pastfib[n-1] = fibx(n-2) + fibx(n-1);
	topfib = n;

	/* now return the fibonacci number */
	return(pastfib[n-1]);
}

/*
 * the interface
 * this does *not* recurse; it checks for errors in n
 * and returns an error code if found
 * otherwise, it calls fibx repeatedly, printing out
 * the fibonacci each step along the way
 *
 * n is numbert of Fibonacci numbers to compute
 */
int fib(int n)
{
	int i;			/* counter in a for loop */

	/* computing negative or no numbers makes no sense */
	if (n <= 0)
		return(0);

	/* set up the array used to hold the numbers */
	init(n);

	/* loop, printing each fibonacci number as it is comnputed */
	for(i = 1; i <= n; i++)
		printf("%d ", fibx(i));
	putchar('\n');
	
	/* clean up the array (not really needed, but good computer hygiene */
	clear();

	/* return success */
	return(1);
}

Matt Bishop Office: 2209 Watershed Sciences Phone: +1 (530) 752-8060 Email: mabishop@ucdavis.edu

ECS 36A, Programming & Problem Solving Version of April 2, 2024 at 12:13PM

You can get the raw source code here.