2.5 Functions and pointers  (Page 8/11)

{

if (n<= 1) return 1;

return (fibonacci(n-1)+ fibonacci(n-2));

}

The output of the above program:

Enter a number: 4

The fibonacci of 4 is: 5

Recursion vs. iteration

In this section, we compare recursion and iteration and discuss why the programmer might choose one approach over the other in a particular situation.

Both iteration and recursion are based on a control structure: Iteration uses a repetition structure; recursion uses a selection structure. Both iteration and recursion involve repetition: Iteration explicitly used a repetition structure while recursion achieves repetition through repeated function calls. Iteration and recursion both involve a termitation test: Iteration terminates when the loop-continuation condition fails; recursion terminates when a base case is recognized. Iteration with counter-controlled repetition and recursion both gradually approach termination: Iteration keeps modifying a counter variable until the counter assumes a value that makes the loop-continuation condtion falil; recursion keeps producing simpler versions of the original problem until the base case is reached. Both iteration and recursion can occur indefinitely: An infinite loop occurs with iteration if the loop-continuation test never become false; infinite recursion occurs if the recursion step does not reduce the problem each time in a manner that converges on the base case.

Recursion has many inconveniences. It repeatedly invokes the mechanism, and consequently the overhead, of function calls. This can be expensive in both CPU time and memory space. Each recursive call causes another copy of the function (actually only the function’s variables) to be created; this can consume considerable memory. Iteration normally occurs within a function, so the overhead of repeated function calls and extra memory assignment is omitted.

Any problem that can be solved recursively can also be solved iteratively (nonrecursively). A recursive approach is normally chosen in preference to an iterative approach when the recursive approach more naturally reflects the problem and results in a program that is easier to understand and debug. Another reason to choose a recursive solution is that an iterative solution is not apparent.

Passing arrays to functions

To pass an array to a function, specify the name of the array without any brackets. For example, if array hourlyTemperature has been declared as

int hourlyTemperature[24];

The function call statement

modifyArray(hourlyTemperature, size);

passes the array hourlyTemperature and its size to function modifyArray.

For the function to receive an array through a function call, the function’s parameter list must specify that an array will be received.

For example, the function header for function modifyArray might be written as

void modifyArray(int b[], int arraySize)

Notice that the size of the array is not required between the array brackets.

Example

To illustrate the use of array and function, we set for ourselves the following tasks:

1. Read in the amount to be deposited in the bank, the interest rate and the number of years to deposit.
2. Invoke the function to compute a table which keeps the amount we get after i years of deposit at the i-th component of the array.
3. Display out the above array