Michele Tomaiuolo Fondamentidi informatica Funzioni C++

(1)

olo – Fondamenti di informaticaolo – Fondamenti di informatica neria dell'informazione – UniPRneria dell'informazione – UniPR .ce.unipr.it/people/tomamic/.ce.unipr.it/people/tomamic/

Funzioni C++

Fondamenti di informatica

Michele Tomaiuolo

tomamic@ce.unipr.it

Input: x

Output: f(x)

(2)

maiuolo – Fondamenti di informaticamaiuolo – Fondamenti di informatica gegneria dell'informazione – UniPRIngegneria dell'informazione – UniPR /www.ce.unipr.it/people/tomamic//www.ce.unipr.it/people/tomamic/

int addition(int m, int n) { int result = m + n;

return result;

}

void fun() { /* procedure */ }

Funzione

Operatore, applicato a operandi, x calcolare risultato

Occorre specificare il tipo di parametri e risulato

Nel corpo: return per terminare e restituire un risultato

Type functionName(Type paramName, Type

paramName…) { /* … */ }

(3)

Funzioni utente

float cube(float x) { float y = x * x * x;

return y;

}

float max(float m, float n) { float result = m;

if (n > m) { result = n; } return result;

}

int main () {

float a; cin >> a;

float b = cube(a);

cout << "The cube is " << b << endl;

cout << "The maximum is " << max(a, b) << endl;

return 0;

}

Parametri formali Parametri formali

Parametri attuali, o effettivi Parametri attuali, o effettivi

(4)

Parametri passati per valore

void swap(int m, int n) { // doesn't work!

int temp = m;

m = n;

n = temp;

}

int main() {

int a = 5, b = 7;

cout << "Before: a=" << a << " b=" << b << endl;

swap(a, b);

cout << "After: a=" << a << " b=" << b << endl;

return 0;

}

// Before: a=5 b=7

// After: a=5 b=7

(5)

Parametri passati per riferimento

Possibile passare parametri per riferimento: &

Modifiche applicate anche alle variabili esterne!

Parametri effettivi: lvalue

void swap(int& m, int& n) { int tmp = m;

m = n;

n = tmp;

}

(6)

Effetti collaterali

Modifica di parametri effettivi (per riferimento) o variabili globali, operazioni di lettura/scrittura...

Annullano la trasparenza referenziale

Impossibile semplificare, sostituendo una chiamata a funzione col suo valore (es. I/O)

Rendono la funzione non idempotente

Richiamata più volte, restituisce valori diversi

→ Difficile fare verifiche matematiche

z = f(sqrt(2), sqrt(2));

s = sqrt(2); z = f(s, s);

(7)

Funzioni non idempotenti

Esempio di semplificazione

int p = rq(x) + rq(y) * (rq(x) – rq(x));

int p = rq(x) + rq(y) * (0) int p = rq(x) + 0

int p = rq(x);

Ma se rq ha effetti collaterali, non si può!

int globalValue = 0; // variabile globale int rq(int x) {

++globalValue;

return x + globalValue;

}

(8)

Regole di visibilità

Ciclo di vita di una var, istruzioni da cui è accessibile Visibilità globale, allocazione statica

Var definite al di fuori di ogni funzione (evitare!)

Visibilità locale alla funzione

Var definite all'interno di una funzione, parametri Allocazione automatica di spazio in stack ad ogni attivazione della funzione (possibile la ricorsione)

Ai primordi (Fortran 66 ecc.) solo allocazione statica:

spazio fisso ed unico per dati locali ad una funzione

Visibilità locale al blocco (e sottoblocchi)

{ int x = 5; cout << x; }

(9)

Programmazione ricorsiva

Molti linguaggi consentono ad una funzione (o procedura) di chiamare se stessa

Chiamata ricorsiva, diretta o indiretta

chiamata diretta chiamata indiretta

int f() { int f() {

…

f();

… }

…

f();

… }

int f() { int f() {

…

g();

… }

…

g();

… }

int g() { int g() {

…

f();

… }

…

f();

…

}

(10)

Fattoriale, ricorsione

Ad ogni invocazione di una funzione, viene creato nello stack un nuovo contesto locale alla particolare attivazione della funzione stessa

int factorial(int n) { int result = 1;

if (n > 1) {

result = n * factorial(n - 1);

} return result;

}

^{N = 4}

RESULT = 1 24 N = 4

RESULT = 1 24 N = 3

RESULT = 1 6 N = 3

RESULT = 1 6 N = 2

RESULT = 1 2 N = 2

RESULT = 1 2 N = 1

RESULT = 1 N = 1

RESULT = 1

(11)

Stack

Pila: memoria dinamica LIFO (Last In First Out)

Dimensione massima prefissata

Il programma ci memorizza automaticamente

Indirizzo di ritorno per le funzioni

Inserito alla chiamata, estratto all'uscita Parametri di funzioni

Inseriti alla chiamata, eliminati all'uscita Variabili locali, alla loro definizione

Eliminate fuori dall'ambito di visibilità

(12)

Record di attivazione

return address return address

parameters parameters

control link control link

saved machine status saved machine status

local data local data temporaries temporaries return address return address

parameters parameters

control link control link

saved machine status saved machine status

local data local data temporaries temporaries return address return address

parameters parameters

control link control link

saved machine status saved machine status

local data local data

fn2() activation

record

fn1() activation

record

main() activation

record

P ro gr am m em or y

Code Code

Global data

Static allocation

Global data

Static allocation

Heap (↓)

Dinamic allocation (new)

Heap (↓)

Dinamic allocation (new)

… …

Stack (↑)

Automatic allocation

Stack (↑)

Automatic allocation

(13)

Stack

main () {

int i, j;

…

fun(j);

♣ … {

int z;

… }

i i j j

void fun(int n) {

int c;

} i i j j ♣ ♣

i i j j ♣ ♣ i i j j

i i j j z z

i i j j stack

n n

n n c c

(14)

I conigli di Fibonacci

Mese 0 → 1

Mese 1 → 1

Mese 2 → 2

Mese 3 → 3

Mese 4 → 5

Mese 5 → 8

(15)

Fibonacci, ricorsione

int fibonacci(int n) { int result = 1;

if (n >= 2) {

result = fibonacci(n-1) + fibonacci(n-2);

}

return result;

}

(16)

Albero delle chiamate

fib(5)

fib(4) fib(3)

fib(3)

fib(2) fib(1)

fib(1) fib(0)

fib(2)

fib(1) fib(0)

fib(2)

fib(1) fib(0)

fib(1)

? ?

(17)

Fibonacci, memoization

int fibonacci(int n) {

static vector<int> lookup(2, 1);

int result = 1;

if (n < lookup.size()) { result = lookup[n];

} else {

result = fibonacci(n - 1) + fibonacci(n - 2);

lookup.push_back(result);

}

return result;

}

lookup: ciclo di vita come una var globale, ma visibile

solo nella funzione lookup: ciclo di vita come una var globale, ma visibile

solo nella funzione

(18)

Fibonacci, iterazione

int fibonacci(int n) { int result = 1;

int fib2 = 1; // result @ 2 steps before for (int i = 2; i <= n; i++) {

result += fib2;

// store previous result, for next step fib2 = result - fib2;

}

return result;

}

(19)

N regine, backtracking

♛

(20)

N regine, ricorsione

bool placeQueens(vector< vector<bool> > & board, int row) { bool result = false;

for (int col=0; col<board[0].size() && !result; ++col) { if (!underAttack(board, col, row)) {

board[row][col] = true;

if (row == board.size() – 1) { result = true;

} else {

result = placeQueens(board, row + 1);

}

if (!result) {

board[row][col] = false;

} } }

return result;

}

Regina in ultima riga:

successo!

Regina in ultima riga:

successo!

Posta una regina in una riga, verifichiamo

le righe successive Posta una regina in una riga, verifichiamo

le righe successive

Non va bene, rimuoviamo la regina

(backtracking)

(21)

N regine, verifica

bool underAttack(vector< vector<bool> > & board, int row, int col) {

bool attack = false;

int dy = -1;

for (int dx = -1; dx <= +1 && !attack; ++dx) { int y = row + dy ; int x = col + dx;

while (0 <= y && y < board.size() && 0 <= x && x < board[y].size() && !attack) { attack = board[y][x];