Lab 10 - Functions in C/C++ | Computer Programming

A C/C++ program is a collection of distinct modules called functions. Splitting the code into small functions, each with a clear responsibility, is the main tool for controlling complexity: it makes the code reusable, testable, and much easier to read.

1Lab objectives

Fig. - The call stack. Each call adds a frame with its parameters, local variables, and return address; on return, the frame disappears and its variables no longer exist.

Writing function definitions and prototypes
Distinguishing pass by value from pass by address
Understanding the call-stack mechanism
Correctly applying scope rules
Implementing recursive functions and recognizing their limits
Using C++ overloading and default parameters

2Definition and prototype

definition syntax

return_type function_name (parameter_list)
{
    <local declarations>
    sequence of statements
}

Element	Role	Notes
`return_type`	the type of the returned value	defaults to `int`; write `void` if nothing is returned
`function_name`	identifier	follows identifier rules
`parameter_list`	declarations of the form `type name`	separated by commas; `void` or empty if there are none

prototype vs. definition

// PROTOTYPE (declaration) - tells the compiler what to expect
double area(double radius);        // placed before main, in the global zone

int main(void) {
    printf("%.2f\n", area(2.5));   // the call is now valid
    return 0;
}

// DEFINITION - the actual body, can also be in another file
double area(double radius) {
    return 3.14159 * radius * radius;
}

Why a prototype is neededThe compiler reads the file top to bottom. Without a prototype, at the point of the call it does not know how many parameters the function has or of what type, so it cannot check correctness. The prototype solves the problem without imposing a particular order on the definitions.

Functions cannot be nestedIn C/C++, unlike Pascal, a function cannot be defined inside another one. All definitions are at the same level.

3Parameter passing

Mode	What the function receives	Modifies the original?	Cost
By value	a copy of the value	no	copying the data
By pointer	the address of the variable	yes	just an address
By reference (C++)	an alias of the variable	yes	just an address
Array	always the address of the first element	yes	just an address

Arrays are the exceptionAn array is never copied on a call. Even when the parameter is written int v[], the function receives a pointer, so changes are reflected in the original array. For the same reason, sizeof applied to the parameter gives the size of a pointer, not of the array - the size must be passed separately.

4Simulator: the call stack

Watch what happens to variables when a function is called: copies are created on the stack, and they disappear on return. Observe why the first version modifies nothing.

5Scope

Variable type	Visible in	Lives
Local (automatic)	the block where it is declared	until exiting the block
Formal parameter	the function body	for the duration of the call
Local `static`	the block where it is declared	the whole program
Global	the whole file, after the declaration	the whole program

Name hidingA local variable with the same name as a global one hides it inside the block. The global one remains accessible in C++ through the scope operator: ::name.

Avoid global variablesThey can be modified from anywhere in the program, which makes it impossible to track down the source of a bug. Prefer explicit passing through parameters.

6Recursion

A recursive function calls itself. Any recursive function must have:

a base case, solved directly, with no recursive call;
a recursive step that approaches the base case with every call.

No base case → stack overflowEvery call consumes space on the stack. If the recursion never stops, the stack is exhausted and the program shuts down abruptly.

Problem	Recursive	Iterative
Factorial	elegant, but uses stack space	more efficient
Naive Fibonacci	very slow - O(2^n), recomputes the same values	O(n)
Tree traversal	natural and clear	needs an explicit stack
Towers of Hanoi	the obvious solution	complicated

7Additional facilities in C++

Facility	Description	Example
Overloading	several functions with the same name, but different parameters	`int max(int,int)` and `double max(double,double)`
Default parameters	values used if the argument is missing at the call	`void f(int a, int b = 10)`
`inline` functions	the code is inserted at the call site	`inline int square(int x)`
References	passing without copying, with simple syntax	`void f(int &x)`

Overloading rulesFunctions must differ in the number or type of parameters. Differing only in the returned type is not enough - the compiler would not be able to choose. Default parameters go only at the end of the list.

8Source code

basic_functions.c - prototypes and calls

#include <stdio.h>

// prototypes
double area(double radius);
int    maximum(int a, int b);
void   printLine(char c, int n);
void   minMax(int v[], int n, int *min, int *max);

int main(void)
{
    printLine('=', 40);
    printf("Area for r=2.5: %.4f\n", area(2.5));
    printf("Maximum of 17 and 42: %d\n", maximum(17, 42));

    int v[] = {29, 10, 14, 37, 5};
    int mn, mx;
    minMax(v, 5, &mn, &mx);          // two results through pointers
    printf("Minimum=%d  Maximum=%d\n", mn, mx);

    printLine('=', 40);
    return 0;
}

double area(double radius) { return 3.14159265 * radius * radius; }

int maximum(int a, int b) { return (a > b) ? a : b; }

void printLine(char c, int n)
{
    for (int i = 0; i < n; i++) putchar(c);
    putchar('\n');
}

void minMax(int v[], int n, int *min, int *max)
{
    *min = *max = v[0];
    for (int i = 1; i < n; i++) {
        if (v[i] < *min) *min = v[i];
        if (v[i] > *max) *max = v[i];
    }
}

recursion.c - comparison with the iterative version

#include <stdio.h>

long factorialRec(int n)
{
    if (n <= 1) return 1;              // BASE CASE - mandatory
    return n * factorialRec(n - 1);    // recursive step
}

long factorialIter(int n)
{
    long r = 1;
    for (int i = 2; i <= n; i++) r *= i;
    return r;
}

long fibonacciRec(int n)               // WARNING: exponentially slow
{
    if (n <= 1) return n;
    return fibonacciRec(n - 1) + fibonacciRec(n - 2);
}

long fibonacciIter(int n)              // linear, much faster
{
    long a = 0, b = 1, t;
    for (int i = 0; i < n; i++) { t = a + b; a = b; b = t; }
    return a;
}

int gcd(int a, int b)                  // Euclid's algorithm
{
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main(void)
{
    printf("10! recursive = %ld\n", factorialRec(10));
    printf("10! iterative = %ld\n", factorialIter(10));
    printf("Fibonacci(20) = %ld\n", fibonacciIter(20));
    printf("gcd(48, 18) = %d\n", gcd(48, 18));
    return 0;
}

overloading.cpp - C++ facilities

#include <iostream>
using namespace std;

// same name, different parameters
int    maximum(int a, int b)             { return (a > b) ? a : b; }
double maximum(double a, double b)       { return (a > b) ? a : b; }
int    maximum(int a, int b, int c)      { return maximum(maximum(a, b), c); }

// default parameters - only at the end of the list
void print(const char *text, int repeats = 1, char separator = '\n')
{
    for (int i = 0; i < repeats; i++)
        cout << text << separator;
}

// passing by reference
void doubleIt(int &x) { x *= 2; }

int main()
{
    cout << maximum(3, 7)        << endl;     // int version
    cout << maximum(3.5, 7.1)    << endl;     // double version
    cout << maximum(3, 7, 5)     << endl;     // three-parameter version

    print("Hello");                          // uses the default values
    print("Test", 3);                        // repeats 3 times
    print("A", 4, ' ');                      // custom separator
    cout << endl;

    int n = 21;
    doubleIt(n);
    cout << "n = " << n << endl;              // 42

    return 0;
}

9Code workshop

For functions, the panel on the right shows the call stack: each call has its own set of variables. With recursion you can see the frames piling up one on top of another.

Recursion - watch the stack grow

#include <stdio.h>

int factorial(int n)
{
    if (n <= 1) return 1;             /* the stopping case */
    return n * factorial(n - 1);      /* the recursive call */
}

int fibonacci(int n)
{
    if (n < 2) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main(void)
{
    printf("5! = %d\n", factorial(5));

    int i;
    printf("Fibonacci: ");
    for (i = 0; i < 10; i++) printf("%d ", fibonacci(i));
    printf("\n");
    return 0;
}

Try thisRun it step by step and stop when several factorial() frames are shown stacked on top of each other: each has its own n. Delete the stopping condition and you will see a stack-overflow error.

10Work tasks

Write functions for the area and perimeter of a circle, rectangle, and triangle.
Implement a function that returns both the minimum and the maximum of a vector at once, through pointers.
Experimentally verify that a function with a parameter passed by value does not modify the original.
Write the recursive and iterative factorial; compare the results for n = 20.
Measure the running time of recursive and iterative Fibonacci, for n = 40.
Implement the greatest common divisor recursively, using Euclid's algorithm.
Write a function that receives an array and print sizeof inside it - explain the result.
In C++, overload a mean-calculation function for 2, 3, and 4 arguments.

11Extended application

ExtensionImplement the Towers of Hanoi problem, printing every move and counting them. Experimentally verify the formula 2^n − 1. Then add a global recursion-depth counter and print the maximum depth reached. Compare the number of calls for naive recursive Fibonacci with the memoized version (which stores already computed results in an array).

Functions in C/C++

1Lab objectives

2Definition and prototype

3Parameter passing

4Simulator: the call stack

5Scope

6Recursion

7Additional facilities in C++

8Source code

9Code workshop

10Work tasks

11Extended application

12Review questions

13Resources