C from the top
7 - Functions 2 & recursion
We have already seen what functions do, but how are they made up?
A function looks like this
The prototype enables the compiler to know what data type is returned and sent to the function and allocate that amount of space for it (remember, different return and variable types require a differing amount of memory). If you don't define the return type, int is assumed. This is fine for a void and int function, but will mess things up if it's a double!
While the compiler can convert from one function type to another, some it can't (for instance, an int to pointer conversion) The prototype enables this sort of error to be caught.
There is a drawback. If you use a multiple file source code (more of these later), the compiler won't catch them.
Due to the fact that C has been around for ages now and was not standardised until 1989, prototypes do not need to be used. This is to maintain backward compatibility. You still need to say what the return type is, but not the prototypes.
The old style declaration looks like this
double amount();
(code)
double amount(double s1, double s2, double s3)
{
return s1+s2*s3;
}
as you can see, the function itself defines the prototype and not the declaration at the beginning of the code. The big problem with not declaring the prototypes in the formal declaration at the start is that the function itself can be sent the wrong number of parameters and the compiler won't generate the error telling you of this. This type of declaration is known as the forward declaration.
This did cause problems when C was standardised. The first was how to get around the old declarations not having a parameter list. This was simply done by the compilers now saying, if nothing is there - nothing can be done about it! There may be parameters, but there may not.
It did not solve the problem though. Say you had the following piece of code using the forward declaration.
void dotted_line()
{
int i;
for (i=0; i<80; i++) printf(".");
}
This will do absolutely nothing, though it is supposed to print a line of dots. It is not down to the old style declaration though.
What was needed is the void statement.
This explicitly tells the compiler that there are no arguments and anything calling this function with arguments is wrong. The codes first line should be
void dotted_line (void)
The second problem comes when C performs an automatic type promotion.
This is when a char is converted to an int, and float to a double. Without the type declarations, this can occur. However, with the declarations made, the automatic type promotions are not made.
The final note to point is that it is possible to make a variable length argument lists. This follow the form
int funct (int a, ... );
This specifies the function funct with one int parameter and a variable number of parameters. This can be very useful! Take printf and scanf, both normally have 2 arguments (say %d and &var). The actual protocol for printf is
int printf(const char * , ...);
the const char * is just the likes of %d, however, it can have as many arguments as you'd like it to have and that is down to the ... preceeding the brackets.
There is only one function without a prototype - main.
main is normally given one of two return types; void and int. void is used when the function returns no values. In ANSI C, main should always a return type int.
In the likes of BASIC, arguments can be passed to the subroutines in one of two ways; call by value and call by reference.
Call by value copies the value passed over into the formal parameter of the subroutine e.g.
PROCdosomething(1001) : : DEFPROCdosomething(a%)
Changes made to the parameter have no effect on the argument (the 1001) used to call it with.
Call by reference is when the address of the argument is copied across to a parameter. The subroutine uses this address to access the argument. Changes made will then effect the original argument.
C uses the call by value as the default, however, you have already seen that by the use of pointers, call by reference can be used. I'm going to use a very nice piece of code here to demonstrate this point.
#include <stdio.h>
void swap (int *i, int *j);
int main(void)
{
int num1, num2;
num1=100;
num2=800;
printf("num1 : %d, num2 : %d\n",num1,num2);
swap(&num1,&num2);
printf("num1 : %d, num2 : %d\n",num1,num2);
return 0;
}
void swap(int *i, int *j)
{
int temp;
temp=*i;
*i=*j;
*j=temp;
}
This routine passes over two integer pointers and swaps them around.
Sending an array across a function can be done in one of three ways, but the function declaration will look different.
You can use
void func_1(int num[5]);
void func_2(int num[]);
void func_3(int *num);
Even though the declarations look differently, the routines are the same. Take a look at this :
#include <stdio.h>
void f1(int num[5]), f2(int num[]), f3(int *num);
int main(void)
{
int numbers[5]={2,4,6,8,10};
f1(numbers);
f2(numbers);
f3(numbers);
return 0;
}
void f1(int nos[5])
{
int loop;
for (loop=0;loop<5;loop++)
printf("%d ",nos[loop]);
}
void f2(int nos[])
{
int loop;
for (loop=0;loop<5;loop++)
printf("%d ",nos[loop]);
}
void f3(int *nos)
{
int loop;
for (loop=0;loop<5;loop++)
printf("%d ",nos[loop]);
}
The outcome is the same no matter what you do, however, the f3 function is the more efficient - it passes over an address, not the array.
Recursion is when a function calls itself until a condition is met.
For instance, the following code prints 9 to 0 by the use of a recursive function.
#include <stdio.h>
void recurse(int i);
int main(void)
{x
recurse(0);
return 0;
}
void recurse(int i)
{
if (i<10)
{
recurse(i+1);
printf("%d ",i);
}
}
What happens though?
The function recurse is first passed 0. Obviously, this is less than 10, so the function is called again with the original number + 1 (so it's now 1). This keeps going until recurse is passed with the number 10. This causes recurse to return to it's previous calling and prints the number 9. recurse then starts calling backwards until 0 is reached (the original call). When this is reached, the function returns to the calling routine and the program terminates.
The recursion can really be thought of here as a spiral. Once you've hit stair 10, you've got to come down to stair 9, then 8 and so on until you're back at the bottom of the stairs.
There is a single problem with a recursive call, and one you may have encountered with some programs. All values are stored on something called the stack. When the recursion is called, all parameters and local variables are stored there. This may seem like no great shakes, but think about it this way. Inside the recursion is an if statement. Without this, the recursion will just go mad and use up all the memory and the program will crash. When this happens you get the immortal internal error; no room on stack. report. And don't we just love seeing that pop up from time to time!
Recursion can be used to copy strings as well. The following does it.
#include <stdio.h>
void rcopy(char *s1, char *s2);
int main(void)
{
char string[80];
rcopy(string,"this is a nice test!");
printf(string);
return 0;
}
void rcopy(char *s1, char *s2)
{
if (*s2)
{
*s1++ = *s2++;
rcopy(s1,s2);
}
else *s1='\0';
}
This works by assigning the character pointed to by s2, to that pointed to by X, then incrementing the pair. This carries on until the end of s2 is reached (this is what the if (*s2) line does). The null terminator is then added onto the end of s1 to tell the program where s1 ends (or in more literal terms, where string ends).
While recursion is fun, it does take a long time for it to execute, an iterative function is more likely to be used.
Recursion can work across functions as well. Take for instance this
#include <stdio.h>
void f1(int a),f2 (int b);
int main(void)
{
f1(30);
return 0;
}
void f1(int a)
{
if (a) f2(a-1);
printf("%d ",a);
}
void f2(int b)
{
printf(".");
if (b) f1(b-1);
}
This will display the following
...............0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
why? and I'll let you puzzle that one out.
Next time, the using the filing system.
Download the examples files here