4. Functions and Recursion – C Programming Essentials

Chapter 4. Functions and Recursion

A large program is often divided into smaller parts called modules. Each module can be realized in the C language with the help of functions. Functions enable people to create their own specific task. A major advantage that C gives us is the ability to create function libraries and then program using only those library functions needed to accomplish the tasks, the program needs to perform. So far, we have been restricting ourselves to a few functions, namely, the main and some standard I/O functions. In this chapter, we shall demonstrate how functions are designed, how two or more functions are put together, and how they communicate with each other.

Introduction

C functions are broadly classified into two major groups – namely, user-defined functions and library functions. The main distinction between the two groups is that user-defined functions are developed by the users for their specific purpose, whereas library functions are a part of the C compiler. Library functions are predefined by the C compiler. Some of the standard I/O library functions have already been discussed in the previous chapters.

In this chapter, we shall be talking more about functions and we will learn how to define functions with parameters. As we proceed, we shall also be demonstrating the methods of retrieving information from a function by returning specific values.

Function calls are just like any other C statement, except that the function call is likely to accomplish the work of several C statements. Functions can be used in conjunction with all C constructs. The C code that describes what a function does is called the function definition, and it has the general form as discussed in Section 2.17. To continue from where we left off in Section 2.17, let us analyse the following program with regard to how functions are executed.

Example . 

Program Ch04n01.c

 /*Program to analyze the working of functions*/

 #include <stdio.h>

 void message()
 {
    printf("Message for you:");
    printf("Have a nice day!\n");
 }

 int main()
 {
    message();
    return 0;
 }
 End Program

Program execution always begins with a main function. When program control encounters a function name, the function is called or invoked. This means that the program control passes to the function. After the function does its work, program control is passed back to the calling environment, which then continues with its work. In the above example, execution begins in main( ). When program control encounters message( ), the compiler knows that a function called message( ) already exists, since it has been defined before main( ). So, the function is invoked and program control is passed to it. After the two printf( ) statements in message have been executed, program control passes back to the calling environment, which in this example is main( ). Since there are no more statements in main( ), the program ends.

Parameters are syntactically identifiers and they can be within the body of the function. Sometimes, the parameters in a function definition are called formal parameters to emphasize their role as placeholders for actual values that are passed to the function when it is called. On function invocation, the values of the arguments corresponding to a formal parameter are used within the body of the executing function.

To illustrate these ideas, let us rewrite the above program so that message( ) has a formal parameter. The parameter will be used to specify the number of times the message will be printed.

Example . 

Program Ch04n02.c

 /*Program demonstrating function parameters*/

 #include <stdio.h>

 void message(int k)
 {
    while(k!=0)
    {
       printf("Message for you:");
       printf("Have a nice day!\n");
       k--;
    }
 }

 int main()
 {
    int n;

    printf("Enter a positive integer: ");
    scanf("%d",&n);
    message(n);
    return 0;
}
End Program

In the above program, the function message( ) has been defined as one that accepts an integer as a solitary argument and returns no value. The main function accepts an integer and reads it into n by calling the scanf function. It then passes the value of n to message( ), and the function message( ) is invoked with the value of its formal parameter, k, set to the value of the actual parameter, n, in the calling function. The called function then executes a loop using the value of k to print k messages on the screen.

In both of the above examples, the called function was defined before the calling function. This enabled the compiler to recognize the called function when it was invoked from the caller. However, there are instances when this ordering is not possible for a set of functions, or the arrangement of the functions in the program somehow necessitate violation of the order of definitions. In such cases, the compiler has to be informed about the existence of a called function before its invocation. Since the function definition occurs later in the program, the solution is to declare a prototype of the called function before the invocation occurs in the program. Although the function prototype declaration had been discussed earlier, we restate the syntax for convenience.

The general syntax of a function prototype declaration in C is:

ReturnType FunctionName (Argument Types List);

Argument Types List is a list of the data types of the argument list as in the function definition and in the same order. If a function has no parameters, then either the keyword void can be used within the parentheses or empty parentheses can be used as an alternative. The other parameters retain the same meaning as in the function definition. Consider the following example that shows how function prototyping can be used.

Example . 

Program Ch04n03.c

 /*Illustration of function prototypes*/

 #include <stdio.h>

 int main()
 {
    int n;
    void message(int);

    printf("Enter a positive integer: ");
    scanf("%d",&n);
    message(n);
    return 0;
 }

 void message(int k)
 {
    while(k!=0)
    {
         printf("Message for you:");
         printf("Have a nice day!\n");
         k--;
    }
 }
 End Program

Consider the function prototype declaration in the above program:

void message(int);

It informs the compiler that the function when called is to be passed as a single argument of type int, and that the function does not return a value. A prototype declaration can be placed in the body of a function where other declarations are used, as in the above example, or it can be placed at the top of the program file as a global declaration.

The function prototype could also be written as:

void message(int k);

In this form, in addition to explicit mention of both the function return types and the parameter list types, extra documentation is also provided for the reader of the program by redundant inclusion of the variable name. The formal parameter variable names need not be the same as those for the function definition. For example, it would not have been erroneous to write:

void message(int n);

Function Arguments

Function arguments have been used, so far, with little explanation, because for the most part, function argument usage is intuitive. The function definition contains an argument list. Items in the list are known as formal arguments. The list may be empty, or contain any number of arguments. The calling function also specifies an argument list to be passed to the function. The arguments in the calling routine are called actual arguments. In general, the number of actual arguments is equal to the number of formal arguments. Most of the high-level languages and C, require a one-to-one match between the actual and the formal arguments lists. The identifiers used as formal arguments are ‘local’ in the sense that they are not recognized outside the function. In other words, they are automatic variables.

There is a different method of formal argument declarations, which is now obsolete. Latest standards of C do not document this form. However, it is presented here only for reference purposes. In this style, the formal argument declarations follow the first line and before the opening brace. The first line contains the return type and name of the function, along with the formal variables enclosed in parentheses. The next line contains the declarations of the formal arguments followed by the body of the function within braces. The now obsolete syntax is presented below for reference to old code:

Return_Type Function_Name(parameter list)
Declarations of the formal parameters;
{
   declarations;
   statements;
}

The return Statement Revisited

We can use C function in two different ways: by doing something with the value returned by the function, or by having the function perform some action but ignoring the return value, if any. When a return statement in a function is encountered, program control immediately passes back to the calling environment. In addition, if an expression follows the keyword return, then the value of the expression is returned to the calling environment as well. This value must agree in type with the function definition header. In previous versions of C, the return type in a function definition could have been excluded and the C compiler assumed the return type as int by default. However, C99 standard requires explicit mention of the return type of a function.

The return statement is optional in a function that does not return a value. If a function that does not return a value contains no return statement, the function returns to its invoker after the final statement in the function body has been executed, and the closing brace encountered.

Thus, in summary, a return statement can have one of the following two forms, where expression is any allowed C expression:

  • return;

  • return(expression);

OR

return expression;

If an expression is provided after the return statement, it may or may not be enclosed within parentheses. In both cases, the function returns the evaluated value of the expression to the caller. The data type of the returned value must match with the return type of the function, as specified in the first line of the function definition. The choice as to include parentheses with the expression following the return statement is left to the programmer to decide. We now summarize the effect of return statements:

  • A return statement effects an exit from a function, and transfers control to the immediate next statement in the calling function.

  • The return statement may include an expression that evaluates to the value returned by the function.

  • If a function includes no return statement, or includes a return statement without an associated value, then the function does not return a value.

  • The caller can choose to ignore the value returned by a function, or it can use the returned value in an expression.

Let us write a program that computes the minimum of two integers using functions:

Example . 

Program Ch04n04.c

 /*Minimum of  two  integers*/

 #include <stdio.h>

 int min(int,int);

 int main()
 {
    int a,b,c;

    printf("Enter two integers: ");
    scanf("%d%d",&a,&b);
    c=min(a,b);
    printf("\n%d is the minimum of %d and %d.\n",c,a,b);
    return 0;
 }
 int min(int a,int b)
 {
    return (a<b)? a: b;
 }
 End Program

Even a small function such as min( ) provides useful structuring of the code. We can similarly write a function, max( ), to return the maximum of two integers. The code is left to the reader as an exercise.

It is noteworthy to mention the return type of main( ). C wants the main function to return an integer value to the calling process. If the executable program is called from the shell, the calling process is generally the operating system. The returned value indicates the exit status of the program. Thus, it is technically equivalent to calling the standard library function exit( ) with the same value as used in the return statement in main. It is not guaranteed that the compiler will return a default value (usually 0) if the return statement is not present in the main function. So, it is useful to always specify the return type of our main function as an int and return the default value of 0 (indicating that the program exited successfully) if required and any other integer value as and when required.

Call-By-Value

Functions are invoked by writing their name and an appropriate list of arguments within parentheses. Typically, these arguments will match in number and type (one-to-one correspondence) with the parameters in the parameter list of the function definition. When we call a function with an argument (an actual parameter), the program copies the argument value into the storage allocated for the corresponding formal parameter. Thus, the function works with a copy of the argument in the function. This means that the function will not change the variables that we have passed as arguments. The information flow via the argument list is, thus, unidirectional as we have seen so far. The function can only get a value rather than an actual variable. Thus, if a variable is passed to a function, the stored value of that variable in the calling environment will not be changed. Such a parameter-passing mechanism is known as call-by-value. In this chapter, all arguments to the functions are passed by the mechanism of call-by-value. This means that each argument is evaluated and its value is used locally in place of the corresponding formal parameters. We shall look closely at a technique of bidirectional parameter passing, or a simulation of call-by-reference after we have discussed pointers.

The following example illustrates call-by-value:

Example . 

Program Ch04n05.c

 /*Sum of first n positive integers, here n=3*/
 #include <stdio.h>

 int sum(int);

 int main()
 {
    int n=3,s;

    printf("%d\n",n);    //Prints 3
    s=sum(n);
    printf("%d\n",n);    //Prints 3
    printf("%d\n",s);    //Prints 6
    return 0;

 }
 int sum(int n)
 {
    int s1=0;

    for(;n>0;--n)
        s1+=n;
    printf("%d\n",n);    //Prints 0
    return s1;
}
End Program

In the above program, even though n is passed to the sum function and the value of n in the body of that function is changed, the value of n in the calling environment remains unchanged, as in the case with local automatic variables. Thus, it is the value of n that is being passed and not n itself. This demonstrates the mechanism of call-by-value.

Stacks in Function Calls

A stack is a data structure where items can be inserted and deleted with certain constraints. The constraints applicable to stacks are enumerated here:

  • A stack is a LIFO (‘last in, first out’ list of items) where the last item inserted (conventionally at the top of the stack) is the first item removed when requested.

  • An insertion (or a push operation in the stack nomenclature) inserts the item at the top.

  • A deletion (or a pop operation in the stack nomenclature) removes the item from the top.

Thus, a stack can be conceptualized as a pipe with one end closed and another (the top end) open. Any push or pop has to be carried out through the single open end and, hence, it acts as a LIFO data structure.

As we know, the code for our program is loaded in memory from storage before execution. Since memory units have addresses, the program is said to be loaded in memory at a specific address. Thus, each compiled instruction is placed at a particular address in memory. When a function call is encountered, the CPU switches execution to the starting address of the invoked function. However, as we have seen, control is switched back to the caller when the invoked function returns. This return is at the exact point where it left off in the caller. It would be very difficult to keep track of the return address and the states of the local variables in the caller, had it not been for stacks.

When a program is in execution, it is allocated a stack (also called the activation stack) for the purpose of storing local variables and keeping track of function calls by storing the return address of the calling function, along with some miscellaneous information like argument count, etc. Together, they constitute the state of a function at a given instant of time. Such information is also termed as an activation record. Each function call creates a new activation record on the stack.

When a program is in execution, the activation record of the currently executing function is present on the top of the activation stack. Thus, at any instant of time, the record at the top of the stack contains the return address (specifying the next instruction to be executed) of the caller of the present function and the current local variables for the function.

When a function call is encountered, the actual parameters for the function call are evaluated. A new activation record is created on the activation stack. The storage (memory) for the formal parameters and local variables of the called function are allocated on the newly created activation record, now on top of the stack. Then, the return address field for the newly created activation record is initialized with the address of the next statement to be executed in the invoked function. The CPU begins execution from the starting address of the called function.

After the invoked function completes its assigned task and returns, the return value (if any) together with the return address of the caller, as stored in the activation record for the completed function, is stored in a temporary section in memory. Then the activation record of the completed function is popped from the activation stack, so that the top of the activation stack now contains the activation record of the caller. The activation record on top is then modified by allocating the return value as stored in the temporary section into the appropriate local variable of the function in its activation stack. The CPU then begins execution with the return address in the temporary section, which gives the location where execution left off in the caller.

The technique is true for any number of function calls to any depth of call – viz. a( ) → b( ) → c( ) → d( )... – as long as the activation stack permits enough space for the storage of activation records of the functions.

The states of the activation stack for successive calls are shown in Figure 4.1, where the function names indicate the activation records for the corresponding functions.

Figure 4.1. The Activation Stack Contents (Step by Step) for the Function-Calling Sequence a( ) → b( ) → c( ) → d( ) → e( )

Recursion

Since recursion is a technique that involves functions, this section has been presented in this chapter. However, the examples in this section require knowledge of arrays. If the reader is new to the language, this section may be skipped at the first reading, without loss of continuity. The reader can then switch back to this section after reading the chapter on Arrays.

Recursion occurs when a function invokes an instance of itself, either directly or indirectly. For starters, a recursive function takes a task. If the task is simple enough to be solved right away, the function solves it and returns control to the calling function. Some programming tasks are naturally solved with the help of recursion, which can be considered an advanced form of flow of control. Recursion is an alternative to iteration. In this chapter, recursion will be explained with some simple example programs. The recursive version of the Towers of Hanoi problem will be discussed graphically. Recursion as an aid to string manipulation will be explained when we deal with arrays.

In C, a function is allowed to call itself. A function is recursive if a statement in the body of a function calls itself. The use of recursion is particularly convenient for those problems that can be defined in naturally recursive terms, though such problems may also be programmed using non-recursive approaches.

A simple example is the function, say fact( ) – to compute the factorial of an integer. By definition, the factorial of a number, n, is the product of all the whole numbers between 1 and n.

For example, the factorial of 3 is calculated as 1*2*3. Both fact( ) functions, in their recursive and iterative versions, are shown in the following programs.

Example . 

Program Ch04n06.c

 /*Iterative (Non-recursive) version of factorial function*/

 #include <stdio.h>

 int fact(int);
 int main()
 {
    int y,n;

    printf("Enter the value of n: ");
    scanf("%d",&n);
    y=fact(n);
    printf("\nFactorial of %d is %d\n",n,y);
    return 0;
 }

 int fact(int n)
 {
    int i,f=1;

    for(i=1;i<=n;i++)
        f*=i;
    return f;
 }
 End Program

Example . 

Program Ch04n07.c

 /*Recursive version of factorial function*/

 #include <stdio.h>

 int fact(int);
 int main()
 {
     int y,n;

     printf("Enter the value of n: ");
     scanf("%d",&n);
     y=fact(n);
     printf("\nFactorial of %d is %d\n",n,y);
     return 0;
 }

 int fact(int n)
 {
     int f;

     if(n==1)
         return 1;
     f=fact(n-1)*n;
     return f;
 }
 End Program

The operation of the non-recursive version of fact( ) is very simple. It uses a loop that starts at 1 and ends at the number, and progressively multiplies each number with the increasing product.

The operation of the recursive fact( ) is to be carefully understood at this point of time. If fact is called with the argument 1, the function returns 1; if it is called with any other argument, it returns the product n*fact(n-1). To evaluate this expression, fact( ) is called with n-1 recursively. This process continues until n equals 2 and the calls to the function begin to return. When we compute the factorial of 2, the first call to fact( ) will cause a second call to be made with the argument of 1. The second call will return 1, which is then multiplied by 2 (the original n value). Thus, the final answer is returned as 2.

A recursive call is similar to a normal function call. However, even though the same function calls itself, a new copy of the function is not created. The same code is shared for multiple entries of the same function on the activation stack. Only the data for the function calls (local variables and execution address point) are different. The activation stack mechanism has, in principle, been slightly modified to be able to accommodate recursion. However, this change is complicated and beyond the scope of this book. The reader can consult a book on ‘compilers’ to know more about the runtime stacks for recursion. At present, our previous discussion on the mechanism behind activation stacks will be enough to understand the issues in implementing and understanding recursion.

At this point, a warning is placed for the reader who might opt for recursion as an alternative to iteration. Since recursion creates new entries on the activation stack and involves the context switch overhead, it might not be efficient to use recursion for all situations where recursion might be used. Although recursive functions are easier to frame (once the technique has been mastered) than their iterative counterparts, iteration is always a better alternative to recursion when the speed of program execution is an important factor. However, recursion often creates elegant code that is easier to understand and conceptualize — especially for solutions to problems that are themselves recursive in nature.

Another thing to note is that a recursive function must never be infinite in its calling mechanism, since stack space is physically limited. An infinite recursive mechanism will run out of stack space sooner or later, and in such situations, the system pops up an ungainly error message after terminating the program abruptly. To avoid this pitfall, a recursive function must always contain a terminating criterion or a base case, often implemented as an if statement, so that the recursive calling mechanism undergoes a return phase at some point of time in the calling sequence. In the previous example, such a return mechanism was effected by the if statement in fact( ). Since the value passed to each recursive call of fact( ) is decremented by an unit at each such call and the initial value passed to fact is an int (which contains a finite integral value limited by the system), the value n=1 is guaranteed at some point in the recursive calling sequence. On encountering this condition at some point in the recursive calling sequence, the condition in the if statement evaluates to true and the value 1 is returned to the caller. The caller returns to where it left off and uses the returned value to evaluate the expression for f. It subsequently returns the value of f and control is passed to the function that called it in turn. Similar steps are performed until the recursive calling sequence of fact( ) has been completed, and the activation record for the first call of fact( ) is popped from the activation stack and control passes back to main( ), where execution resumes from where it left off (after the point where fact() was called).

Any function may be recursive, except for main( ), which cannot invoke an instance of itself. Although some old (and now, obsolete) compilers may allow this strange and non-standard syntax, newer C compilers will not allow this to happen. It is advisable not to use this technique to ensure portability of programs among the different compilers available.

Analysing recursive implementations further, the reader will observe the basic philosophy of recursive implementations as being a bottom-up approach to the solution. In most cases, the base case is the clue behind devising a recursive solution to a problem. The base case returns the base solution, and consecutive returns of a mathematical function of the returned value are propagated successively upward. It, thus, contributes to the generation of the solution, until the final solution is computed when the recursive mechanism ends, and the activation record for the initial call to the recursive function is popped from the activation stack.

For another simple and explanatory example of recursion, we present a recursive solution to the problem of computing the sum of the first n positive integers.

Example . 

Program Ch04n08.c

 /*Recursive version of the sum of the first n integers*/

 #include <stdio.h>

 int sum(int);

 int main()
 {
    int s,n;

    printf("Enter the value of n: ");
    scanf("%d",&n);
    s=sum(n);
    printf("\nSum of the first %d integers is %d.\n",n,s);
    return 0;
 }

 int sum(int n)
 {
    if(n <= 1)
        return n;
    else
        return (n + sum(n-1));
 }
 End Program

The execution trace of sum( ) for successive recursive calls is shown in the Figure 4.2. Since the above example is a bottom-up solution, the base case needs to be considered first, since the solution is built up from the base case and is propagated upwards through return statements to build the final solution.

Table 4.2. Values Produced by Return from Recursive Calls to Sum ( )

Function Call

Value Returned

sum (1)

1

sum (2)

2 + sum (1) = 2 + 1 = 3

sum (3)

3 + sum (2) = 3 + 3 = 6

sum (4)

4 + sum (3) = 4 + 6 = 10

sum (5)

5 + sum (4) = 5 + 10 = 15

sum (6)

6 + sum (5) = 6 + 15 = 21

...

...

sum (n)

n + sum (n - 1)

Note that the variable n (in the recursive call to sum( ) in the else part) is reduced by 1 from the value of n received at the previous instance of the recursive invocation, on each call to sum( ). The working of the program is easy to trace from Figure 4.2 and shall not be explained further.

The remainder of this section will involve different examples on recursion to illustrate the powers and pitfalls of using this technique.

The following program prompts the user to type in a line and then reprints the line backwards by means of recursion.

Example . 

Program Ch04n09.c

 /*Displaying an input line backwards by recursion*/

 #include <stdio.h>

 void display();

 int main()
 {
    printf("Input a line : ");
    display();
    printf("\n");
    return 0;
 }

 void display()
 {
    char ch;

    if((ch = getchar()) != '\n')
        display();
    putchar(ch);
 }
 End Program
EXECUTION (Boldface represents user input)

Input a line : tbok jump wft tis fzb
bzf sit tfw pmuj kobt

The invocation of the recursive function display( ) occurs after a prompt to the user. The input is requested and is provided as a line terminated by the newline character (since the return key is pressed at the end of the input line). As each character is read in within display( ), it initiates a new call to display( ) without printing the character read in. Each call creates a new activation record having its own local storage for the variable ch. This local ch, local to a particular invocation of display( ), is where the individual characters of the line will be stored. The recursive calls continue until a newline character is read at a particular invocation. Each invocation of display( ) now returns and prints the value stored in its local variable ch in a bottom-up fashion. Thus, first the newline character is printed, and then the character just preceding it, and so on, until the first character is printed. As an effect, the input line is printed in reverse order.

The next three examples are easy enough to understand at this point in the chapter, so we present them with no explanation behind their mechanisms. The readers are expected to understand and trace the programs on their own.

Moving on to our next example, it is well known that multiplication of two positive integers can also be implemented with repetitive addition. For example, 8 * 4 can be implemented as 8 + 8 + 8 + 8. The following program performs this task recursively.

Example . 

Program Ch04n10.c

 /*Multiplication through repeated addition – recursive version*/

 #include <stdio.h>

 int mul(int,int);

 int main()
 {
    int a,b;

    printf("Enter the values of a and b : ");
    scanf("%d%d",&a,&b);
    printf("\nProduct = %d\n",mul(a,b));
    return 0;
 }

 int mul(int a,int b)
 {
    if(a==0 || b==0)
        return 0;
    return (a + mul(a,b-1));
 }
 End Program

The greatest common divisor (GCD) was first encountered in Chapter 1. The greatest common divisor of two positive integers is the largest integer that is a divisor of both of them. For example, 6 and 15 have 3 as their GCD. The following recursive program computes the GCD of two positive integers.

Example . 

Program Ch04n11.c

 /*Use of a recursive function to compute the GCD of two positive
 integers*/

 #include <stdio.h>

 int gcd(int,int);

 int main()
 {
    int a,b;

    printf("Enter the values of a and b : ");
    scanf("%d%d",&a,&b);
    printf("\nGCD = %d\n",gcd(a,b));
    return 0;
 }

 int gcd(int p,int q)
 {
    int r;

    if((r=p%q)==0)
        return q;
    else
        return gcd(q,r);
 }
 End Program

We now move on to using a recursive function, say fib( ), to compute a Fibonacci number. Fibonacci numbers are elements of a series given by the recursive definition:

fib(i) = fib(i-1) + fib(i-2)        for all i>2

The base cases are:

fib(1) = 1
fib(2) = 1

Thus, fib(3) = fib(2) + fib(1) = 1 + 1 = 2.

It is easy to compute that the first few numbers of this series would be:

1, 1, 2, 3, 5, 8, 13, 21 ...

The program is presented below with a table afterwards to help trace the program.

Example . 

Program Ch04n12.c

 /*Program to compute a specified Fibonacci number using recursion*/

 #include <stdio.h>

 int fib(int);

 int main()
 {
    int n;

    printf("Enter the value : ");
    scanf("%d",&n);
    printf("\nFib(%d) = %d\n",n,fib(n));
    return 0;
 }

 int fib(int n)
 {
    if(n > 2)
        return (fib(n-1) + fib(n-2));
    else
        return 1;
 }
 End Program

The returned values produced at each recursive call from fib(1) to fib(6) is given in Figure 4.3.

Table 4.3. Values Produced by Return from Recursive Calls to fib( )

Function Call

Value Returned

fib (1)

1

fib (2)

1

fib (3)

fib(2) + fib(1) = 1 + 1 = 2

fib (4)

fib(3) + fib(2) = 2 + 1 = 3

fib (5)

fib(4) + fib(3) = 3 + 2 = 5

fib (6)

fib(5) + fib(4) = 5 + 3 = 8

There is a problem with the efficiency of the above program. The order of growth of the recursive algorithm followed is exponential. This is due to the fact that for an initial call to fib(5), say, we have the computation tree for recursion as shown in Figure 4.4.

Figure 4.4. Computation Tree for Call to fib(5)

The problem that is immediately visible from the tree diagram is that fib(3) is being calculated twice. The value already produced for fib(3) on the left branch of the root node cannot be used by the one on the right and has to be recalculated. This results in repeated computations of the same value. The complexity of the above tree can be shown to be exponential in nature. This is a major pitfall that recursion brings in. When execution time is of importance, one can ill-afford to write a recursive routine such as the one in Ch04n12.c, since repeated and unnecessary calculations are being brought into play due to the use of recursion. The larger the input, the more time it takes to compute the solution. The above program becomes more inefficient as the input value increases. To give an idea about the exponential growth of the function-calling mechanism in the above program, we present a slightly modified version to record each call to fib( ). It is identical to the earlier version in all other respects.

Example . 

Program Ch04n13.c

 /*Program to compute a specified Fibonacci number using recursion - modified*/

 #include <stdio.h>
 long ncalls=0;

 long fib(int);

 int main()
 {
    int n;

    printf("Enter the value : ");
    scanf("%d",&n);
    printf("\nFib(%d) = %ld.",n,fib(n));
    printf("\nNo of calls to the function : %d\n",ncalls);
    return 0;
 }

 long fib(int n)
 {
    ncalls++;
    if(n > 2)
        return (fib(n-1) + fib(n-2));
    else
        return 1;
 }
 End Program

The above program produces the following output:

For n=10, fib(10) is 55;

the number of calls to fib( ) is printed as 100.

For n=20, fib(20) is 6765;

the number of calls to fib( ) is printed as 13529.

For n=30, fib(30) is 832040;

the number of calls to fib( ) is printed as 1664079.

Note that the number of calls to fib( ) gets unacceptably high even for a relatively small value of n. This problem can be easily avoided by using iteration in place of recursion. It is left to the reader as an exercise to write the iterative version of the above program.

Towers of Hanoi—Case Study of Recursion

Towers of Hanoi is a popular children’s game, consisting of three poles and a number of different sized discs. Initially, the discs are stacked on the leftmost pole in order of their size, with the largest disc on the bottom and the smallest on the top. Let the poles be named as Peg A, Peg B, and Peg C from left to right. Assume that there are n discs. The objective of the game is to transfer the discs from the leftmost pole (Peg A) to the rightmost pole (Peg C) without ever placing a larger disc on top of a smaller disc. Only one disc can be moved at a time, and each disc must always be placed over any one of the poles.

To obtain a solution for the above problem, the following approach may be adopted:

  1. First move the top (n-1) discs from Peg A to Peg B via Peg C.

  2. Move the nth disc from Peg A to Peg C.

  3. Move the (n-1) discs from Peg B to Peg C via Peg A.

Thus, we find that the solution is inherently recursive and can be implemented using recursion. As an example, if there is only one disc, the 1st and the 3rd steps are not applicable, and step 2 accomplishes the task. The program is presented below, after which we shall be going into a more detailed explanation of what is happening with the discs and the way the algorithm works.

Example . 

Program Ch04n14.c

 /*A recursive solution to the towers of Hanoi problem*/

 #include <stdio.h>

 void Hanoi(int, char, char, char)

 int main()
 {
    char src,aux,dest;
    int n;

    src='A';
    aux='B';
    dest='C';

    printf("Enter the number of discs in the game : ");
    scanf("%d",&n);
    if(n == 0)
        printf("\nNothing has to be moved.\n");
    else
        Hanoi(n,src,aux,dest);
    return 0;
 }
 void Hanoi(int n,char src,char aux,char dest)
 {
    if(n == 1)
        printf("Move disc from peg %c to peg %c.\n",src,dest);
    else{
        Hanoi(n-1,src,dest,aux);
        Hanoi(1,src,aux,dest);
        Hanoi(n-1,aux,src,dest);
    }
 }
 End Program

The solution is explained pictorially assuming three values of n (n=1, n=2, n=3) in the figures from Figure 4.5 to Figure 4.19. However, the approach is similar for larger values of n.

Figure 4.5. Pegs of the Towers of Hanoi

Figure 4.6. Initial Condition – Only One Disc at Source (Prior to Transfer)

Figure 4.7. Move Disc 1 from Source to Destination (Solution Reached)

Figure 4.8. Initial Condition – Two Discs at Source

Figure 4.9. Move Disc 1 from Source to Auxiliary

Figure 4.10. Move Disc 2 from Source to Destination

Figure 4.11. Move Disc 1 from Auxiliary to Destination (Solution Reached)

Figure 4.12. Initial Condition – Three Discs at Source

Figure 4.13. Move Disc 1 from Source to Destination

Figure 4.14. Move Disc 2 from Source to Auxiliary

Figure 4.15. Move Disc 1 from Destination to Auxiliary

Figure 4.16. Move Disc 3 from Source to Destination

Figure 4.17. Move Disc 1 from Auxiliary to Source

Figure 4.18. Move Disc 2 from Auxiliary to Destination

Figure 4.19. Move Disc 1 from Source to Destination (Solution Reached)

The program flow for the Towers of Hanoi (for n=3) can be pictorially viewed in the Figure 4.20.

Figure 4.20. Program Flow for the Towers of Hanoi with 3 Discs

Efficiency Considerations for Use of Functions

Since function calls and returns involve operations on stacks, a function call is slower than an equivalent inline code (a code where the function is not used as a separate entity; rather, the function statements are embedded in place of each function call); there is a trade-off between using too many functions and using too little functions. Code length is sizeably reduced when functions are used instead of inline code. This is true for functions involving many lines of code which are called frequently in the program. However, it is ill advised to write a function for a task if the task is to be performed only once or twice in the program. However, if it is known that a future use of the task may be in place for other programs, or for future modifications of the same program, the task may be placed in the code as a function. A function is also appropriate even if it is to be invoked for only a few times in the program, if the task performed by the function is discrete enough to be grouped under a separate module. Using adequate number of functions improves code readability. However, unnecessary usage of too many functions should be avoided, unless the process is unavoidable otherwise.

The trade-off between the two techniques demands selection of the technique based on programming experience and expertise. As the reader becomes more comfortable in writing large programs, he will automatically adopt any of the techniques as and when required. However, the reader is expected to analyse the coding of a solution well enough to identify the functions, required to perform the task.

Summary

A C program is essentially made up of a number of interacting functions, designed to carry out specific tasks. A function in C is very much like a mathematical function, since it accepts multiple arguments and returns a value (optional). C uses the technique of call-by-value for its arguments. The call-by-reference technique is absent in C, although it can be simulated by using pointers, as we shall see in the chapter on Pointers.

Stacks are an essential feature in the function-calling mechanism. Activation stacks are used to store the return address and the return values of a function. The values for a function are stored as items on the stack and are called activation records. Function calls can be performed to any depth, limited only by the maximum space available for the activation stack.

Recursion is a useful technique for solving inherently repetitive (recursive) problems. This technique leads to more elegant code in some circumstances, but should be avoided whenever execution time of the program is a constraint.

New Terminology Checklist

Message

Arguments

Return

Revisited

Call

GCD

Recursion

Stack

Exercises

1.

Write a function gcd to compute the GCD of two integers.

2.

The Fibonacci sequence a(1), a(2), a(3), ..., a(n), ... is defined by

  • a(1) =1

  • a(2) = 1

  • a(n) = a(n–1) + a(n–2), for all n > 2

This generates the sequence

  • 1, 1, 2, 3, 5, 8, 13, 21, ...

Write a C function fibonacci(...) that computes the Fibonacci number corresponding to its positive integer argument, so that, for example, fibonacci (7) is 13.

3.

What is the difference between function and recursion in C language?

4.

Write a function to carry out the task of computing

  1. The factorial of a number

  2. The permutation nPr.

  3. The combination nCr.

  4. The LCM (Least Common Multiple) of a number.

5.

Write a function tobin to display an integer in its binary format.

6.

Write a function countone to count the number of 1’s in a character (byte).

7.

Write a function isprime to check, if a number is prime.

8.

Write a function to convert a binary number to its equivalent decimal number.

9.

Write a recursive routine to reverse the digits of an integer and return the result as an integer.

10.

Trace the Towers of Hanoi solution for n = 4 and verify that the solution is correct.