REVISED: Sunday, March 15, 2015

CONTENTS:
• I. C FACTORIAL INTRODUCTION
• II. RECURSION
• III. ANALYSIS OF RECURSION EXAMPLE PROGRAM
• IV. RECURSION EXAMPLE PROGRAM SOURCE CODE
• V. C FACTORIAL REFERENCES

YOU WILL LEARN:
1. C recursion techniques.
2. How to write a C recursion program.

I. C FACTORIAL INTRODUCTION

Hello; nice to meet you. Welcome to the “C Factorial Tutorial”

II. C RECURSION

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.

III. ANALYSIS OF C RECURSION EXAMPLE PROGRAM

A. Nested Parenthesis

One way to understand recursion is to think of each recursive function call as creating a nested set of parenthesis. The first recursive function call is the outermost set of parenthesis. Each subsequent recursive function call is a new nested set of inner parenthesis. The base case recursive function call is the innermost set of nested parenthesis. To solve the recursion you have to start with the base case innermost parenthesis and work your way outward through each nested set of parenthesis.

Think of each set of nested parenthesis as a C code block with its own scope and local variables stored on the runtime stack. The top of the runtime stack contains the base case scope and recursive function call local variables. When you solve the base case you exit that scope and return to the next scope of nested local variables which have moved to the top of the runtime stack. This process is repeated as you work your way outward through every scope of nested parenthesis comprising the recursive function calls.

The example program uses this process as follows:

(The 1st recursive call is the outermost set of parenthesis which multiplies 8 by 8-1 factorial. (The 2nd recursive call is an inner set of parenthesis which multiplies 7 by 7-1 factorial. (The 3rd recursive call is an inner set of parenthesis which multiplies 6 by 6-1 factorial. (The 4th recursive call is an inner set of parenthesis which multiplies 5 by 5-1 factorial. (The 5th recursive call is an inner set of parenthesis which multiplies 4 by 4-1 factorial. (The 6th recursive call is an inner set of parenthesis which multiplies 3 by 3-1 factorial. (The 7th recursive call is an inner set of parenthesis which multiplies 2 by 2-1 factorial. (The 8th recursive call is the innermost base case set of parenthesis which multiplies 1 by 1-1 factorial.))))))))

B. Playing Computer

Playing computer is very tedious; therefore, please bear with me.

The example program computes 8 factorial by solving the innermost parenthesis first and then working outwards solving subsequent nested parenthesis until 8 factorial is computed.

(The 1st recursive call is the outermost set of parenthesis which multiplies 8 by 8-1 factorial. (The 2nd recursive call is an inner set of parenthesis which multiplies 7 times 6 times 5 times 4 times 3 times 2 times 1.))

(The 1st recursive call is the outermost set of parenthesis which multiplies 8 times 7 times 6 times 5 times 4 times 3 times 2 times 1.) Completing the multiplication gives us 8 factorial or 40,320.

IV. C RECURSION EXAMPLE PROGRAM SOURCE CODE

#include<ctype.h>
/*
Character Class Tests
*/

#include<stdio.h>
/*
Standard I/O.
*/

#include<stdlib.h>
/*
Utility Functions.
*/

/*
DECLARATIONS
*/

#define HEADER \
"\n\n FACTORIAL\n" \
" C RECURSION TUTORIAL\n" \
" PART 1\n\n" \
" EXAMPLE OF A RECURSIVE FUNCTION COMPUTING 8 FACTORIAL\n"

char nxt;

/*
FUNCTION PROTOTYPES
*/

int factorial( unsigned int stack );

int main( int argc, char* argv[] )
{
printf( HEADER );

int x = 8;

char nxt;

printf( "\n\n Successive stack multiplication is performed; the factorial of %d is %d.", x, factorial(x) );

printf( "\n\n Press any key to continue: " );

nxt = getchar();

return 0;
}

/*
FUNCTION DEFINITIONS
*/

int factorial( unsigned int stack )
{
printf( "\n\n " );

/*
Base case.
*/
if( stack <= 1 )
{
printf( "Recursive call places multiplication by %d on the stack.", stack);

printf( "\n\n Press any key to continue: ");

nxt = getchar();

return 1;

}else
{
printf( "Recursive call places multiplication by %d on the stack.", stack );

printf( "\n\n Press any key to continue: " );

nxt = getchar();

return ( stack * factorial( stack - 1 )); /*
Recursive call.
*/
}
}

V. C FACTORIAL 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).

YOU HAVE LEARNED:
1. C recursion techniques.
2. How to write a C recursion program.

Elcric Otto Circle

-->

-->

-->

How to Link to My Home Page

It will appear on your website as:
"Link to ELCRIC OTTO CIRCLE's Home Page"

C TUTORIALS

Thursday, September 22, 2011

FACTORIAL

How to Link to My Home Page

No comments:

Post a Comment