5.6 RECURSION

Recursion is a process by which a function calls itself repeatedly,until some specified condition has been satisfied.The process is used for repetitive computations in which each action is stated in terms of a previous result.Many iterative (i.e. repetitive) can be written in this form.

Here is a program that calculates the factorial of a given input quantity using recursion.

/*calculate the factorial of an integer quantity using recursion*/

#include stdio.h

long int factorial (int n);     /*function prototype*/

main()

{

int n;

long int factorial (int n);

/*read in the integer quantity*/

printf ("n= ");

scanf ("%d", &n);

/*calculate and display the factorial*/

printf ("n!=%d\n", factorial(n));

}

long int factorial (int n)        /*calculate the factorial*/

{

if (n <= 1);

return(1);

else

return (n * factorial (n-1));

}

The main portion of the program simply reads the integer quantity n and then calls the long-integer recursive function factorial..The function factorial calls,itself recursively, with an actual argument (n-1) that decreases in magnitude for each successive call.The recursive calls terminate when the value of the actual argument becomes equal to 1.

When the program is executed ,the function factorial will be accessed repeatedly,once in main and (n-1) times within itself ,though the person using the program will not be aware of this.Only the final answer will be displayed;for example

n=10

n!=3628800

5.5 PASSING ARGUMENTS TO A FUNCTION

When a single value is passed to a function via an actual argument,the value of the actual argument is copied to the function.Therefore,the value of the corresponding formal argument can be altered within the function, but the value of the actual argument within the calling routine will not change.This procedure of passing the value of an argument to a function is known as passing by value.

Here is a simple C program containing a function that alters the value of its argument.

#include stdio.h

void modify (int a)   /*function prototype*/

main()

{

int a=2;

printf("\na=%d (from main, before calling the function)", a);

modify(a);

printf("\na=%d (from main, after calling the function)",a );

}

void modify(int a)

{

a*=3;     

printf("\na=%d (from the function, after being modified)",a );

return;

}

The original value of  a (i.e. a=2) is displayed when the main begins execution.This value is then passed to the function modify,where it is multiplied by 3 and the new value is valued.Note that it is the altered value of  the formal argument that is displayed within the function.Finally,the value of a within main (i.e. the actual argument) is again displayed,after control is transferred back to main from modify.
When the program is executed the folloing output is generated.

a=2 (from main, before calling the function)

a=6 (from the function, after being modified)

a=2 (from main, after calling the function)

These results show that a is not altered within the main,even though the corresponding value of a is changed within modify.


Passing an argument by value has advantages and disadvantages.On the plus side,it allows a single valued actual argument to be written as an expression rather than being restricted to a single variable.Moreover, if the

actual argument is expressed simply as a single variable,it protects the value of  this variable from alteration within the function.On the other hand, it does not allow information to be transferred back to the calling portion of program via arguments.Thus, passing by value is restricted to a one-way transfer of information.

 

5.4 FUNCTION PROTOTYPES

In the programs that we have examined earlier in this chapter,the programmer defined function has always preceded the main.Thus,when these programs are compiled,the programmer defined function will have been defined before the first function access.However, many programmers prefer a "top-down" approach,in which the main appears ahead of the programmer defined function definition.In such situations the function access (within main) will precede the function definition.This can be confusing to the compiler,unless the compiler is first alerted to the fact that the function being accessed will be defined later in the program.A function prototype is used for this purpose.

Function prototypes are usually written at the beginning of a program,ahead of any programmer defined functions (including main).The general form of a function prototype is

data-type name (type 1 arg 1,type 2 arg 2,.........,type n arg n);

where data-type represents the data type of the item that is returned  by the function,name represents the function name, and  type 1, type 2,............., type n represent the data types of the arguments arg 1,         arg 2,...., arg n.Notice that a function prototype resembles the first line of a function definition (though a function prototype end with semicolon).

Function prototypes are not mandatory in C.They are desirable,however, because they further facilitate error checking between the calls to function and the corresponding function definition.

5.3 ACCESSING A FUNCTION

A function can be accessed (i.e. called) by specifying its name,followed by a list of arguments enclosed in parentheses and separated by commas.If the function call does not require any arguments,an empty pair of parentheses must follow the name of the function.

The arguments appearing in the function call are referred to as actual arguments,in contrast to the formal arguments that appear in the first line of the function definition.(They are also known simply as arguments,or as actual parameters).In a normal function call,there will be one actual argument for each formal argument.Each actual argument must be of the same data type as its corresponding formal argument.Remember that it is the value of each actual argument that is transferred into the function and assigned to the corresponding formal argument.

If the function returns a value,the function access is often written as an assignment statement.e.g

y=polynomial(x);

This function access causes the value returned by the function to be assigned to the variable y.

On the other hand,if the function does not return anything,the function access appears by itself.

e.g display(a,b,c);

This function access causes the value of a,b, and c to be processed internally (i.e. displayed) within the function.

The following program determines the largest of three integer quantities.This program makes use of a function that determines the larger of two integer quantities.

/*determine the largest of three integer quantities*/

#include stdio.h

int maximum (int x, int y)     /*determine the larger of two integer quantities*/

{

int z;

z= (x >= y)? x: y;

return(z);

}

main()

{

int a,b,c,d;

/*read the integer quantities*/

printf("\na=");

scanf("%d", &a);

printf("\nb=");

scanf("%d", &b); 

printf("\nc=");

 scanf("%d", &c);

/*calculate and display the maximum value*/

d=maximum(a,b);

printf("\n\maximum=%d", maximum(c,d));

}


The function maximum is accessed from two different places in main.In the first call to maximum the actual arguments are the variables a and b,whereas the arguments are c and d in the second call (d is a temporary variable representing the maximum value of  a and b ).
Note the two statements in main that access maximum i.e.

d=maximum(a,b);

printf("\n\maximum=%d", maximum(c,d)); 

These two statements can be replaced by a single statement

printf("\n\maximum=%d", maximum(c,maximum(a,b))); 

In this statement we see that one of the calls to maximum is an argument for the other call.Thus the calls are embedded,one within the other, and the intermediary variable, d,is not required.

5.2 DEFINING A FUNCTION

A function definition has two principal components:the first line (including the argument declarations), and the body of the function.

The first line of a function definition contains a type specification of the value returned by the function,followed by the function name and (optionally) a set of arguments,separated by commas and enclosed in parentheses.Each argument is preceded by its associated type declaration.An empty pair of parentheses must follow the function name if the function definition does not include any arguments.

In general terms, the first line can be written as

data-type name (type 1 arg 1,type 2 arg 2,.........,type n arg n)

where data-type represents the data type of the item that is returned by the function, name represents the function name and type 1,type 2,.......,type n represent the data types of the arguments arg 1,              arg 2,......,argn.The data types are assumed to be of type int if they are not shown explicitly.

The arguments are called formal arguments, because they represent the names of data items that are transferred  into the function from the calling portion of the program.they are also known as parameters or formal parameters.(The corresponding arguments in the function reference are called actual arguments,since they define the data items that are actually transferred. )The identifiers used as formal arguments are "local" in the sense that they are not recognized outside the function.Hence the name of the focal arguments need not be the same as the names of the actual arguments in the calling portion of the program.Each formal arguments must be of the same data type,however, as the data items it receives from the calling portion of the program.

The remainder of the function definition is a compound statement that defines the action to be taken by the function.This compound statement is sometimes referred to as the body of the function.Like any other compound statement,this statement can contain expression statements,other compound statements,control statements,and so on.It should include one or more return statements,in order to return a value to the calling portion of the program.

In general terms, the return statement is written as

return expression;

A function can access other functions.In fact,it can even access itself (this process is known as recursion.)

5.1 A BRIEF OVERVIEW

A function is a self contained program segment that carries out some specific, well defined task.Every C program consists of one or more functions.One of these functions must be called main.Execution of the program will always begin by carrying out the instructions in main.Additional functions will be subordinate to main, and perhaps to one another.

If a program contains multiple functions,their definitions may appear in any order,though they must be independent of one another.That is,one function definition cannot be embedded within another.

A function will carry out its intended action whenever it is accessed (i.e. whenever the function is "called") from some other portion of the program.The same function can be accessed from several different places within a program.Once the function has carried out its intended action,control will be returned to the point from which the function was accessed.