the Technology Interface / Winter98

RECURSION

by

Thomas Jenkins
tjenkins@nmsu.edu
Engineering Technology
New Mexico State University

Abstract

This is the source code for a program which will demonstrate the concept of recursion through programming examples of several common mathmetical algorithms. Recursion is a fundamental concept in mathemetics and computer science and many practical co mputations can be fitted to a recursive framework. Simply, a recursive function (program or algoritm) is one which calls itself as part of the function body.
Description

An essential ingredient of recursion is there must be a "termination condition"; i.e. the call to oneself must be conditional to some test or predicate condition which will cease the recursive calling. A recursive program must cease the recursion o n some condition or be in a circular state, i.e. an endless loop which will "crash" the system.

In a computer implementation of a recursive algorithm, a function will conditionally call itself. When any function call is performed, a new complete copy of the function's "information" (parameters, return addresses, etc.. ) is placed into general dat a and/or stack memory. When a function returns or exits, this information is returned to the free memory pool and the function ceases to actively exist. In recursive algorithms, many levels of function calls can be initiated resulting in many copies of th e function being currently active and copies of the different functions information residing in the memory spaces. Thus recursion provides no savings in storage nor will it be faster than a good non-recursive implementation. However, recursive code will o ften be more compact, easier to design, develop, implement, integrate, test, and debug.

References

"Algorithms in C", Robert Sedgewick, Addison Wesley, 1990
"Structured C for Technology", Adamson, Merrill, 1996
"The C programming Language", Bernighan and Ritchie, Prentice Hall 1978
"C for Engineers and Scientists", G. Bronson, West, 1993
"Programming Languages:", T. Pratt, Prentice-Hall, 1975

Usage

This program is built and compiled under ANSII standard TURBO C, and is executed from the MSDOS command line: TECH_TIP

User instructions are displayed and inputs accepted. See input and variable list below.

Version and Change History

Version 1.0 R&D 10/20/97 -twj
V1.1 - added additional comments 10/25/97 -twj
V1.2 - added numberic base conversion example 11/10/97 -twj
V1.3 - added programmers comment block 11/20/97 -twj
V1.4 - added Fibonnaci sequence example 11/30/97 -twj
V1.5 - made more compact and effecient 12/05/97 -twj

Copywrite @1997 1998 Thomas Jenkins, Associate Professor, NMSU

Constraints and Known Errors:

Algorithms:

4!= 4 x 3 x 2 x 1 = 24

2)the exponitial (POWER) function X^N
Example:

3³ = 3 x 3 x 3 = 27

3)calculate the equation:

ⁿ

^n-1

^n-2

^n-3

4)conversion of any integer decimal number (base 10)
to another number base integer. Bases are limited to 2-16.

5)the FIBONACCI sequence:

Fib(N) = Fib(N-1) + F(N-2) for N1, and Fib(0) = Fib(1) = 1
example:

Additional examples of common recursive algorithms which are not shown here are: binary searchs of arrays, divide and conquer techniques, data structure search techniques, geometric fractals generation, approximation algorithms, conversion of numbers to character strings and vice versa, displaying in reverse order, binary tree traversal, sorting techniques, etc....... In fact, almost all iterative algorithms (for.., do.., and do....while loops) can be designed and implemented as recursive algorithms.

Requirements:

Variable List:

- see local declarations below.

System Functions Called:

User Functions:

long fact(int x)	factorial recursive function
long power( long x, int exp)	x raised to the n power recursive fct.
long rec(int y, int x)	- see above algorithm #3
int convert(int n, int base);	number conversion recursive fctn.
int fib(int n)	recursive Fibonacci sequence generation
int input_em(int x, int n)	this will enter and verify a number between MIN and MAX. NOT recursive.

Programmers Description:

The user is asked to choose a recursive algorithm from a menu. Then the user is prompted for input variables for the mathematical algorithm which is the demonstration recursive function. These values are the "seed" variables for the recursive algorithms. A function is called from the main() function which will initiate the recursive algorithm. This function will test a termination condition and either return a value (or error code) or will call itself with modified parameters. The process is repeatable.

Two keys to each recursive function are: a test of a "termination condition" which controls if the function will call itself or stop the recursion; and, each call to itself (the recursive function) must modify the parameters to pass to the next iteration of the function. These parameters will be part or all of the termination condition.



/*********************** INCLUDE LIBRARIES   ***************************/

#include <stdio.h>
#include <conio.h>

/*****************          DEFINES         ***************************/
#define MAX 10
#define MIN  1

/*****************   DECLARE USER FUNCTIONS    ************************/
/*                    recursive functions                             */
long fact(int x);
long power( long x, int exp);
long rec(int y, int x);
int convert(int n, int base);
int fib(int x);

/*                 non-recursive utility functions                    */
int input_em(int x, int n);

/*******************   DEFINE MAIN ROUTINE    ***********************/
void main(void)
{
/* local input, termination and seed variables for algorithms      */
	int x=0, n=0;
	unsigned long sum;
	char c;

/*** clear screen, display user headings and instructions    ***/
	do{
		clrscr();
		puts("\n\t\t TECH_TIP.C RECURSION DEMONSTRATION PROGRAM ");
		puts("\t\tCopywrite 1998 (c) NMSU Thomas Jenkins\n\n");
		printf("This program will demonstrate the concept of recursion ");
		puts("using these examples:");
		puts("\n 1)   X factorial (X!)\n");
		puts(" 2)   X raised to a power N\n");
		puts("               n    n-1    n-2    n-3           1");
		puts(" 3)   value = x  + x  +   x  +   x     ..... + x \n" );
		puts(" 4)   Conversion of a decimal number to any base 2-16\n");
		puts(" 5)   Fibonacci sequence element generation\n\n");

		printf("Enter the number of your choice (1-5) to view:");
		c=getch();
		clrscr();
		flushall();
		puts("\n\t\t TECH_TIP.C RECURSION DEMONSTRATION PROGRAM ");

/*** Act on the menu selection by chosing the appropriate case. ***/
		switch(c)
		{

/********************************************************************/
/*** 					X factorial  (X!)											***/
/********************************************************************/
		case '1':
		puts("\tThis will demonstrate the X FACTORIAL recursive algorithm\n");

/*** get an integer X (1-10) and check its validity				***/
		puts("For the variable X in X!,");
		x = input_em(MIN,MAX);

/*** calculate X factorial using recursion and display results   ***/
		printf("\nFor X = %d\t\t", x);
		printf("X!(factorial) = %ld",fact(x));
		break;

/********************************************************************/
/*** Exponitial or "x" raised to the power n.							***/
/********************************************************************/
		case '2':
		puts("\n\tDemonstrates recursion using an exponitial algorithm, or");
		puts("\t\t\t X raised to a power N.\n");

/*** Enter an integer value 1-10  (X) and validity check			***/
		puts("For the X variable,");
		x = input_em(MIN,MAX);

/*** get the power (N) to raise the integer (X) to:		*/
		printf("\nEnter the power (the exponent) to raise %d to:\n",x);
		n = input_em(MIN,MAX-1);

/*** invoke the recursive function to determine X raised to the power N.
	  and display results					***/
		printf("\n%d raised to the %d power is: ", x, n);
		printf(" %lu\n", power(x,n));
		break;

/********************************************************************/
/*** This will do recursion demo for the following algorithm #3:	***/
/********************************************************************/
		case '3':
		puts("\n\nDemonstrates recursion using the equation example:");
		puts("           n    n-1    n-2    n-3           1");
		puts("  value = x  + x  +   x  +   x     ..... + x\n\n");

/*** get an integer X (1-10) and check its validity				***/
		puts("For the variable X");
		x = input_em(MIN,MAX);

		puts("\nEnter the integer value for the exponent n:");
		n = input_em(MIN,MAX-1);

/*** Calculate the value for the algorithm and display			***/
		printf("For x = %d\t and n = %d",x,n);
		printf("\t Value = %lu \n",rec(n,x));
		break;

/********************************************************************
		 This will do a recursive demo of number system base conversion.
		 The basic algorithm is repeated division of the number by the base
		 with the whole number remainder of the division being the LSD of
		 the converted value.
/********************************************************************/
		 case '4':
		 puts("\n\n\t\tExample of BASE conversion using RECURSION\n\n");

/* enter a decimal value which will be converted to another base */
		 x=input_em(MIN, 32767);

/* enter the base to convert the decimal number to					 */
		 printf("\nEnter the base (2-16) to convert %u decimal to:\n",x);
		 n=input_em(2,16);

/* convert the decimal number to the new base system and display ***/
		 printf("\nThe converted base %d equivalent of %u decimal is:",n,x);
		 printf("%0x",convert(x,n));
		 break;

/********************************************************************/
/*** This will demo the Fibonacci sequence using a recursive algorithm
	  This will conpute and display the Nth element in the sequence.
/********************************************************************/
		case '5':
		puts("\n\tDemonstrates recursion using a Fibonacci sequence.\n\n");

/*** Enter an integer value 1-20  (X) and validity check			***/
		puts("Enter the Nth element in the sequence to compute and display:");
		x = input_em(MIN,MAX*2);

/*** call the function for sequence generation ***/
		printf("\n\nThe %dth element in the Fibonacci sequence is: ",x);
		printf("%d",fib(x));
		break;

		default: break;
		} /*** end switch   ***/
		puts("\n\n\nHit the SPACE BAR to EXIT, any other key to repeat");
  }while (getch() !=' ');
}
/***           E N D   O F   M A I N ( )                    ***/


/********************************************************************/
/**            USER DEFINED FUNCTION DEFINATIONS                   **/
/********************************************************************/

/********************************************************************/
/*** 					X factorial  (X!)											***/
/* This function will recursively call itself until the parameter
	is less than two(2) (the termination condition).

	The recursion algorithm for factorial is:
		  FACT_X = X * (X-1) * (X-2) * (X-3) ..... * 1   ,or
		  FACT_X = X * (X-1)! for X0 and 0! =1;

	The recursive algorithm is to repeatively multiply a value (X) by
	the value-1 (X-1), then X = X-1, then repeat (recursion) until X = 1.
	The termination condition is if the parameter(X) is less than or equal
	to 1. The parameter (X) which is passed to the next function is the
	parameter passed to THIS version of the function minus one(1).

	The final result is the factorial of the parameter (X).  */
/********************************************************************/
/********************************************************************/
long fact(int x)
{
	/** Termination Condition: 1! or 0! = 1, so stop the recursion, i.e.
			(don't call itself anymore.)								**/
		if (x <= 1)
			return(1);
		else
	/** call itself (recursion) but change the parameter to pass (X-1) */
			return( x * fact(x-1));
}

/********************************************************************/
/********************************************************************
 *** Exponitial (POWER) or "X" raised to the power N.							***
	  This function will recursively call itself decrementing the exponent
	  variable until the exponent is zero. The final value returned is
	  the value X raised to the exponent power N. Termination condition
	  is if the exponent is zero.
/********************************************************************/
/********************************************************************/
long power (long x, int exp)
{
	if (exp <= 0)									/* Termination Condition */
		return(1);
	else
		return( x * power(x,--exp));       /* Recursion  */
}

/********************************************************************/
/********************************************************************/
/* Demo of recursion for the above equation #3:

	NOTE: this uses the previously defined recursive function "power"
			within this function. A recursive function calling another
			recursive function within the body of this function - nested
			recursive functions.													  */
/********************************************************************/
/********************************************************************/
long rec(int n, int x)
{
	if (n0){									/* termination condition for */
		return(power(x,n)+rec(--n,x));   /* the exponent of zero(0)   */
	}
	return(0);
}


/********************************************************************/
/********************************************************************
	  This recursive function will convert and display
	  any decimal number (base 10) converted to any other number base
	  value. The converted base is anything between 2 (BINARY) and 16 (HEX)

	  This function uses the concept of "repeated division of the base"
	  to do the number conversion. The modulo operator (%) is used to
	  generate the whole number remainder of division resulting in the
	  LSD for each iteration of the division. The quotient of the division
	  is the parameter for the next iterations.
/********************************************************************/
/********************************************************************/
int convert(int n, int b)
{
	if (n !=0){
		printf("%0x",convert(n/b,b));
		return(n%b);
	}
	else
		return (0);
}

/********************************************************************/
/********************************************************************
	This will generate the Xth element in the Fibonacci sequence
	using a recursive algorithm:

	Fib(X) = Fib(X-1) + Fib(X-2), for X 1 and Fib(0) = Fib(1) = 1.
/********************************************************************/
/********************************************************************/
int fib(int x)
{
	if (x<=1)                         /* termination condition */
		return(1);
	else{
		 return(fib(x-1) + fib(x-2));  /* recursive call        */
	}
}

/********************************************************************/
/********************************************************************/
/* This function will input and test an integer value between MIN-MAX
	This is a non-recursive utility function.
/********************************************************************/
/********************************************************************/
int input_em (int min, int max)
{
int x,err=0;

/*** Enter an integer value between MIN <-> MAX and validity check ***/
		while (err!=1){
			printf("Enter a decimal integer value between %d and %d: ",min,max);
			err=scanf("%d",&x);
			if ((x<min) || (x>max) || (err!=1)){
				err=0;
				printf("Illegal Entry!! RETRY\n");
				flushall();
			}
		}
		return(x);
}
/*** end tech_tip.c program ***/