Functions


Definition of a function

  • Function call:

  • Arguments are expressions that substitute parameters in a call: function parameters are initialized with the values of the arguments.

Example 1:

We define a function that computes (returns) for a natural number n, the sum of the first n natural numbers.

Iterative way (repetitive): suma: Z -> Z, suma(n)=1+2+3+…+n

int suma(int n)
{
  int s = 0;
  int i;
  for(i=1; i<=n; ++i)
    s += i;
  return s;
}

Recursive way: suma: Z -> Z, suma(n)=1+2+3+…+n

int suma(int n)
{
  if (n==0) 
     return 0;
  else
     return n+suma(n-1);
}

Example 2 – What’s happening?

void swap(int x, int y){
   int temp = x; x = y; y = temp;
   cout << "x=" << x<< ",y=" << y<< "\n";
}

int main(void){
   int a = 2, b = 3;
   swap(a, b);   // x = 3, y = 2
   cout << "a=" << a<< ",b=" <<b <<"\n";
   // a = 2, b = 3

Example 2 – What’s happening?

void swap(int& x, int& y){
   int temp = x; x = y; y = temp;
   cout << "x=" << x<< ",y=" << y<< "\n";
} 
int main(void){
   int a = 2, b = 3;
   swap(a, b);   // x = 3, y = 2
   cout << "a=" << a<< ",b=" <<b <<"\n";
   // a = 3, b = 2

Passing parameters

Global and local variables

Explanations on example, in classroom

Parameters passed by value

Parameters passed by reference

Returning a value using the parameter passed by reference  – „procedures”

Returning a value with return „with function type”

Examples:

  1. Write a function that verifies if the binary representation of a number x is palindrome: bool isPalindrome(unsigned int x).
#include<iostream>
 using namespace std;

// This function returns true if the k'th bit from x is 1(is set).
 // For example, if number is (0010) 2 and k is 2, then it returns true.
 bool isKthBitSet(unsigned int number, unsigned int k)
 {
    return (number & (1 << (k-1)))? true: false;
 }

// This function returns true if the binary representation of x is palindrome
 // For example, (1000...001) is paldindrome.
 bool isPalindrome(unsigned int number)
 {
    int left = 1; // Initialize the position from left.
    int right = sizeof(unsigned int)*8; // Initialize the position from right.

    // Compare bits one by one.
    while (left < right)
    {
       if (isKthBitSet(number, left) != isKthBitSet(number, right))
          return false;
       left++; right--;
    }
    return true;
 }

// Test program of the above function
 int main()
 {
    unsigned int x = 1<<15 + 1<<16;
    cout << isPalindrome(x) << endl;
    x = 1<<31 + 1;
    cout << isPalindrome(x) << endl;
    return 0;
 }

2) Write a recursive function that computes the factorial of a natural number n.

Plan

  • One-dimensional arrays, declaration, names, initialization
  • Array storing, their use as function arguments
  • Character arrays, macros and functions for arrays
  • Two-dimensional arrays
  • Pointers, pointer expressions, pointer arithmetics

Arrays

  • Collection of variables of the same type, being called with the same name – array components
  • Components are identified and accessed with the help of indices
  • An array uses contiguous memory locations, in indices order
  • Arrays:
    • One-dimensional (1 – dimensional): character arrays
    • Two-dimensional (2 – dimensional)

One-dimensional arrays

type nameArray[dimension];

necessary_bytes = sizeof(type)* dimension

#define NMAX 25

int a[NMAX]; // int a[25];

  • Storing order– indices order: 0, 1, …, NMAX-1;
  • Array elements– in contiguous memory locations (side by side);
  • Operations are made using components, with forwhile or do-while iterations:
   for (i=0; i<n; i++) a[i]=0; 
   for (i=0; i<n; i++) c[i]=a[i]+ b[i];

Name of an array

  • Name of an array:
    • variable name;
    • pointer to the first element of the array:

       a       equivalent to &a[0]      *a  equivalent to  a[0]

       a+1 equivalent to &a[1]       *(a+1) equivalent to  a[1]

       a+2 equivalent to &a[2]      *(a+2) equivalent to  a[2]

       a+i equivalent to &a[i]         *(a+i) equivalent to  a[i]

Initialization of a one-dimensional array

Storing an array

Iterate through an array

We have an array of numbers. We wish to compute the sum of its elements, after we initialized the sum with 0. We can iterate through array a, using multiple ways.

Arrays as function arguments

  • An array CANNOT be passed ENTIRELY as an argument to a function.
  • Arrays are passed as arguments using a pointer to an array.
  • The formal parameter of a function that has an array can be declared as:
    • Pointer
    • Array with dimension
    • Array without dimension
  • Example 1
    • Let’s consider that we have an array i and we call a function functia with the argument i.
    • In this case, functia can have one or more of the following headers, in which the argument can be: pointer to an integer, an array with a specified number of integer elements, an array with an unspecified number of integer elements.

  • Example 2
    • In this example, the function insert_sort  has an array with an unspecified number of integer elements as argument.
    • Because argument a[]  is equivalent to pointer *a, the function will modify the elements of array a, making an insertion sort of the elements of a, having n elements.

  • Example 3
    • In this example, we suppose that function suma will compute the sum of the n elements of array a.
    • We can have the header of the function in two ways. The first argument is either a[], either *a, so a pointer to the beginning of the array.
    • In the first call, suma(v,100), the function will compute the sum of the 100 elements in the array, starting with the element on position 0 (and finishing with the element on position 99).
    • In the second call, suma(v,8), it will compute the sum v[0]+v[1]+…+v[7].
    • In the third call, the first argument is the address of the element on position 4 in the array, so the sum will be calculated as v[4]+v[5]+… + v[k-6-1+4] (total k-6 elements).
    • In the fourth call, the first argument (v+4)  is equivalent to the argument &v[4], that means it will also compute v[4]+v[5]+… .

Character arrays

  • Character arrays are one-dimensional arrays of type char.
    • Each element of the array is a character.
    • The last character of the array is the null character ‘\0’. It marks the end of the array.
  • Example:
    • char sir[10];
    • This is a declaration of a 9 character array (sir[0], sir[1]…, sir[8]), to which  it is added sir[9], that will mark the end of the array.
    • The 10th character is the null character ‘\0’ (or NULL or 0).

Array declaration

Array declaration with initialization

Assigning and comparing character arrays

  • Asigning “=” only at declaration:
    char sir[10];
    sir = "Hello";// wrong
    char sir[10] = "Hello";// OK
  • Comparation is not possible with “==” operator
    char sir_unu[10] = "white";
    char sir_doi[10] = "black";
    sir_unu == sir_doi;   // warning: operator has no effect
  • A function strcmp is used
    strcmp(s,t) will return  0, if s and t are identical, a number <0, if s is lexicographic before t, a number >0, if s is lexicographic after t.

Macros and functions for arrays

Two-dimensional arrays

tip numeTablou[m][n];
int a[m][n];
  • Contiguous memory of m×n locations
  • Components are identified using 2 indices:
    • First index has values{0, 1, …, m -1}
    • Second index has values {0, 1, …, n -1}
    • The component variables: a[0][0], a[0][1], …, a[0][n-1], a[1][0], a[1][1], …, a[1][n-1], …, a[m-1][0], a[m-1][1], …, a[m-1][n-1]
  • The order of storing the components is given by the lexicographic order of indices

  • In the figure above, is of type int[2][3], a[0] is of type int[3], a[1] is of type int[3], and each element in the matrix is of type int.

Iterating through a two-dimensional array

double a[MMAX][NMAX]; // declaration of two-dimensional array. 

double suma;  // sum of array elements

/* . . . */

for (i = 0; i < m; i++)
    for (j = 0; j < n; j++)
        cin >> a[i][j];

suma = 0;
for (i = 0; i < m; i++)
    for (j = 0; j < n; j++)
         suma += a[i][j];

Two-dimensional arrays

  • With the analogy from matrix, a 2-dimensional array can be seen as a 1-dimensional array with each component being a 1-dimensional array.
  • Notation:
a[0][0], a[0][1], …, a[0][n-1],…, a[m-1][0], a[m-1][1],…, a[m-1][n-1]

Two-dimensional arrays seen as one-dimensional arrays

Accessing elements of a 2-dimensional array

 

Expressions equivalent to a[i][j]

Two-dimensional arrays as arguments

int minmax(int t[][NMAX], int i0, int j0,
        int m, int n)
{
  //...
}

/* usage */
if (minmax(a,i,j,m,n))
{
   // ... 
}

Array initialization (vectors, arrays, matrices)

int a[] = {-1, 0, 4, 7};
/* equivalent to */
int a[4] = {-1, 0, 4, 7};
char s[] = "un sir";         /* equivalent to */
char s[7] = {'u', 'n', ' ', 's', 'i', 'r', '\0'};
int b[2][3] = {1,2,3,4,5,6}  /* equivalent to */
int b[2][3] = {{1,2,3},{4,5,6}} /*equivalent to*/
int b[][3] = {{1,2,3},{4,5,6}}

Pointers

  1. Pointer = variable that contains a memory address, which is a localization of an object (often other variable)
  2. Offer the possibility of modifying the function call arguments
  3. Allow dynamic allocation
  4. Can improve efficiency of some routines
  5. Uninitialized pointers
  6. Pointers that contain inadequate values

Declaration of a pointer variable:

type *name_pointer;

  • name_pointer is a variable that can have as values, memory addresses which contain values with the base type type.
  • Examples:
int *p, i;  // int *p; int i;
p = 0;
p = NULL;
p = &i;
p = (int*) 232;

Semnification of p = &i;

  • p “points to i”, “cointains/ receives the address of i”, “refers to i”.

The opreator of dereferencing (indirection) * :       int *p;

  • p is pointer, *p is/ receives the value of the variable that has address p

The direct value of p is the address of a location, and *p is the indirect value of p: which is stored in that location

int a = 1, *p;

p = &a;

  • because it stores addresses, the length of memory locations do not depend on the type of the associated variable

sizeof(int*) = sizeof(double*) = …

  • pointer display:

Pointer expressions
 

#include <iostream>
using namespace std;
int main(void){
    int i=5, *p = &i;
    float *q;
    void *v;
    q = (float*)p;
    v = q;
    cout << "p = " << p << ", *p = " << *p << "\n";
    cout << "q = " << q << ", *q = " << *q << "\n";
    cout << "v = " << v << ", *v = " << *((float*)v)<<"\n";
    return 0;
}

Pointer arithmetics

Video presentation of the link between pointers and arrays

https://youtu.be/ASVB8KAFypk