06 - Recursion, pointers and references

Recursive functions

In C++, the functions can call themselves. Let’s start with the example. Imagine, you need to compute the sum of numbers from 1 to n. It is possible to write a program:

#include <iostream>

int sum(int n) {
    if (n == 1) {
        return n;
    }
    return n + sum(n - 1);
}

int main() {
    std::cout << sum(5);
}

The program computes the sum from 1 to n by computing the sum from 1 to n-1 and adding n. Each recursive function has:

• ending condition to stop recursion,
• line in the function that calls itself.

Calling the sum function with value 5 as n argument will result in the program performing following operations:

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

sum(5) = 5      +     4     +      3      +     2      +     1 = 15

🔨 🔥 Assignment 🔥 🔨

Create a function that computes the n-th Fibonacci number recursively.

Pointers

Variables have a specific place in memory. It is possible to work directly with the places in memory. To get the address (place in memory) of the variable, we can use ampersand sign (&):

int a = 5;
int *b = &a; // b stores the memory address of variable a
std::cout << &a << "==" << b << std::endl;

The type int * means that the variable is a pointer to a specific memory location that has int variable in it. To get the value from the address of memory (dereference the pointer), we can use asterisk sign (*):

int c = *b; // c now is equal to 5
std::cout << a << "==" << *b << "==" << c << std::endl;

Arrays are closely related to pointers (they are simplified syntax for working with pointers):

int arr[4] = {1, 2, 3, 4};
int *arr_pointer = arr;
if (*(arr_pointer + 2) == arr[2]) {
   std::cout << "Equal" << std::endl;
}

In this example, we create an array of 4 integers. Then, we create a pointer and initialize it with arr, which is the name of the array. For arrays, the name of the array is a pointer to the first element of the array. The index of an array is a memory offset.

Difference between reference and pointer

A reference variable is an alias, that is, another name for an already existing variable. It is advised to use references instead of pointers when possible, as it is easier to avoid problems with memory management.

Creating a reference

double value = 13.5;

double &value_reference = value;

Creating a pointer

double value = 13.5;

double *value_pointer = &value;

Passing arguments by reference

#include <iostream>

void divide_value(double &value) {
   value /= 2; // changes the original value
}

int main() {
   double value = 7.5;
   divide_value(value);

   std::cout << value << std::endl;

   return 0;
}

Passing arguments by pointer

#include <iostream>

void divide_value(double *value) {
   *value /= 2; // changes the original value
}

int main() {
   double value = 7.5;
   divide_value(&value);

   std::cout << value << std::endl;

   return 0;
}

Changing memory location the reference points to is impossible:

Once a reference was created, it will forever be tied to the same original variable.

double first_value = 7.5;
double second_value = 10.75;

double &value_reference = first_value;
value_reference = second_value; // changes first_value to 10.75, does NOT tie value_reference to second_value

std::cout << value_reference << std::endl;
std::cout << first_value << std::endl;

Output:

10.75
10.75

Changing memory location the pointer points to:

double first_value = 7.5;
double second_value = 10.75;

double *value_pointer = &first_value; // value_pointer points to address of first_value
value_pointer = &second_value; // now value_pointer points to address of second_value

std::cout << *value_pointer << std::endl;
std::cout << first_value << std::endl;

Output:

10.75
7.5

Creating reference to nothing is impossible:

char &char_ref; // Invalid code

Creating pointer to nothing (called empty or null pointer):

char *char_ptr = nullptr; // Valid code

ATTENTION Dereferencing a pointer that points to nothing (null pointer) will cause the program to crash.

Passing arrays to functions

There are three ways of passing arrays to functions. We will only use one of them:

void do_sth_with_array(int *arr) {
    /* ... */
}

When passing an array to a function there is usually a need for the function to know how many elements the array contains. The header of such function looks as follows:

void do_sth_with_array(int *arr, int arr_size) {
...
}

It is possible to use arrays passed to functions the same way as in previous classes.

🔨 🔥 Assignment 🔥 🔨

Create a function that returns the smallest value in an array that is passed as an argument to that function.

More information about functions can be found here.

Final assignments 🔥 🔨

Exercise 1

Create a function that replaces small letters with capital letters in an array passed to that function.

Exercise 2

Create a function that takes an array as a parameter and sorts the array using bubble sort. Swapping of the values should be done using additional function called swap.

Exercise 3

Create a function that takes the text as a parameter and prints the statistics of letters to the console, e.g.:

Input text:

AAA aaa b BB

Expected output:

A: 3 a:3 b:1 B: 2

Homework 💥 🏠

1. Create a function that computes and returns the harmonic mean of values stored in an array. The function takes two parameters - an array of unrestricted size and an array size stored as an integer.
2. Write two functions: one that ciphers and one that deciphers a text passed as an array. During ciphering, the i-th letter from the alphabet should be exchanged for the i-th letter from the end of the alphabet, i.e. A is changed to Z (Z to A), C to X and X to C. The ciphering/deciphering should leave all non-letter characters it encounters untouched.

Authors: Michał Fularz, Rafał Kabaciński, Piotr Kaczmarek, Michał Nowicki, Mikołaj Wasielica, Jan Wietrzykowski, Dominik Pieczyński