Page 1 of 1

FIBONACCI SERIES C RECURSION TUTORIAL PART 2 Rate Topic: -----

#1 Elcric  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 102
  • View blog
  • Posts: 453
  • Joined: 02-May 09

Posted 17 August 2010 - 12:29 PM

FIBONACCI SERIES
C RECURSION TUTORIAL
PART 2

CONTENTS
• I. INTRODUCTION
• II. FIBONACCI SERIES
• III. ANALYSIS OF EXAMPLE PROGRAM
• IV. EXAMPLE PROGRAM
• V. REFERENCES


I. INTRODUCTION

Hello; nice to meet you. Welcome to the “Fibonacci Series - C Recursion Tutorial - Part 2.”

II. FIBONACCI SERIES

The Fibonacci series begins with 0 and 1 followed by Fibonacci numbers which are the sum of the previous two Fibonacci numbers. For example, the first 26 numbers of the Fibonacci series are as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, and 75025.

A Fibonacci problem might be to determine what the 10th number in the series is. The 10th number is the sum of the 8th and 9th numbers. The nth number is the sum of n - 2 and n - 1, as long as n > 2. A recursive function is a function that calls itself and must have at least one exit condition called a base case that can be satisfied or the recursive function will continue to call itself repeatedly until the runtime stack overflows. In the Fibonacci series, n < 3 is a stop condition.


III. ANALYSIS OF EXAMPLE PROGRAM

When you execute the example program be careful! If you enter too large a number for the series, you might run out of memory! The maximum number of values the example program can generate before it overflows depends on both the amount of memory you have in your system and any changes you make to the example program data types, i.e., from int to double or long. I used the int data type because int uses the least amount of memory. If you change the program data type to a double or a long it will lower the maximum number of values the program can generate before it overflows because they both use more memory than an int datatype.

Using the algorithm that the nth number in the Fibonacci series F(n) is the sum of F(n – 2) and F(n – 1), as long as n > 2, we can show the recursive calls required for the first 5 Fibonacci numbers F(5) as follows:

F(0) has no recursive call, it returns 0 the first number in the Fibonacci series.

F(1) has no recursive call, it returns 1 the second number in the Fibonacci series.

F(2) has no recursive calls: F(2-1) + F(2-2) = F(1) + F(0) = 1 the third number in the Fibonacci series.

F(3) has 2 recursive calls: F(3-1) + F(3-2) = F(2) + F(1) = 2 the fourth number in the Fibonacci series.

F(4) has 6 recursive calls: F(4-1) + F(4-2) = F(3) + F(2) = 3 the fifth number in the Fibonacci series.

F(5) has 14 recursive calls: F(5-1) + F(5-2) = F(4) + F(3) = 5 the sixth number in the Fibonacci series.

This can also be shown graphically as follows:

………………………..F(5)
………………….../………….\
……………...F(4)……………….....F(3)
…………../……..\...................../……..\
……….F(3)……...F(2)…………...F(2)…….F(1)
.……/……\........./……\.........../…....\
….F(2)….F(1)….F(1)….F(0)….F(1)….F(0)
…/……\
F(1)….F(0)


IV. EXAMPLE PROGRAM

/*
	FIBONACCI SERIES
	C RECURSION TUTORIAL
	PART 2
*/

#include<ctype.h>     /*  Character Class Tests  */
#include<stdio.h>     /*  Standard I/O.          */
#include<stdlib.h>    /*  Utility Functions.     */

/*
	DECLARATIONS
*/

int recursiveCalls = 0;

#define HEADER \
    "\n\n  FIBONACCI SERIES\n" \
	"  C RECURSION TUTORIAL\n" \
	"  PART 2\n\n" \
	"  EACH FIBONACCI NUMBER IS THE SUM OF THE PREVIOUS TWO FIBONACCI NUMBERS.\n"

/*
	FUNCTION PROTOTYPES
*/

int fibonacci( int stack );

int main( int argc, char* argv[] )
{
	int i = 0;
	int loop = 1;
	int stack = 0;
	printf( HEADER );

	do
	{
		recursiveCalls = 0;

		do
		{
			printf("\n\n  How many Fibonacci series numbers do you want to compute?");
			printf("\n\n  Type a positive nonzero integer then press Enter:  ");
			scanf( "%d", &stack);

		}while( stack <= 0 );

		printf("\n\n  The Fibonacci series of %d numbers is:  ", stack);

		for( i = 0; i < stack; i++ )
		{
			/*
				Recursive call.
			*/
			printf(" %d ", fibonacci(i));
		}

		printf("\n\n  There were %d recursive calls.", recursiveCalls);

		printf( "\n\n  Press 1 then Enter to continue or 9 then Enter to Exit:  " );

		scanf("%d", &loop);

	}while( loop == 1 );

	return 0;
}
	
/*
	FUNCTION DEFINITIONS
*/

int fibonacci( int stack )
{
	if( stack == 1 || stack == 0 )
	{
		return stack;
	}else
	{
		recursiveCalls += 2;
		/*
			Recursive call.
		*/
		return ( fibonacci( stack - 1 ) + fibonacci( stack - 2 ));  
	}

	return 0;
}



V. REFERENCES

The C Programming Language by Brian Kernighan and Dennis Ritchie (Englewood Cliffs, N.J.: Prentice-Hall, 1978).

The C Programming Language Second Edition by Brian Kernighan and Dennis Ritchie (Upper Saddle River, N.J.: Prentice-Hall PTR, 1988).


Is This A Good Question/Topic? 1
  • +

Page 1 of 1