Aula 5

Sobrecarga de nomes de rotinas

Rotinas recursivas

Invocação de rotinas

2003/2004Introdução à Programação2

Sobrecarga de nomes de rotinas

Quadrado de um inteiro (int):int quadradoDe(int const valor){ return valor * valor;}

Quadrado de um valor de vírgula flutuante (double):double quadradoDe(double const valor){ return valor * valor;}

Quadrado de um inteiro (long):long quadradoDe(long const valor){ return valor * valor;}

2003/2004Introdução à Programação3

Assinatura de uma rotina

Assinatura de uma rotina: Nome Lista dos tipos dos parâmetros

Não pode existir mais do que uma rotina com a mesma assinatura

2003/2004Introdução à Programação4

quadradoDe():assinaturas e invocações

Assinaturas quadradoDe, int quadradoDe, double quadradoDe, long

Invocações cout << quadradoDe(10) << endl; // int cout << quadradoDe(10.0) << endl; // double

cout << quadradoDe(10L) << endl; // long

2003/2004Introdução à Programação5

somaDe()

int somaDe() {     return 0; }

int somaDe(int const a) {     return a; }

int somaDe(int const a, int const b) {     return a + b; }

int somaDe(int const a, int const b, int const c) {     return a + b + c; }

2003/2004Introdução à Programação6

somaDe():assinaturas e invocações

Assinaturas: somaDe somaDe, int somaDe, int, int somaDe, int, int, int

Invocações: cout << somaDe() << endl; cout << somaDe(1) << endl; cout << somaDe(1, 2) << endl; cout << somaDe(3, 2, 1) << endl;

2003/2004Introdução à Programação7

somaDe(): parâmetros com argumentos por omissão

int somaDe(int const a = 0, int const b = 0, int const c = 0) {     return a + b + c; }

2003/2004Introdução à Programação8

Factorial

n! = n n - 1 ... 1 se 0 < nn! = 1 se n = 0

n! =

n! = (P i : 1 ≤ i ≤ n : i )

n

∏ ii = 1

2003/2004Introdução à Programação9

Factorial de forma recorrente

n! = ... (n - 1)! ...

4! = 4 3 2 1 = 4 (3 2 1) 4! = 4 3!

n! = n (n - 1)!

Esta definição é válida sempre? E se n for 0? 0! = 0 (-1)! = 0 ???????

2003/2004Introdução à Programação10

Definição do factorial

Matematicamente de forma recorrente

n! = n (n - 1)! se 0 < nn! = 1 se n = 0

Em C++

? factorialDe( ? ) { ?}

2003/2004Introdução à Programação11

factorialDe()

/** Devolve o factorial do inteiro não negativo passado como argumento.     @pre  0 ≤ n.     @post factorialDe = n!. */ ? factorialDe( ? ) { assert( ? );

?}

2003/2004Introdução à Programação12

factorialDe()

/** Devolve o factorial do inteiro não negativo passado como argumento.     @pre  0 ≤ n.     @post factorialDe = n!. */ int factorialDe(int const n) { assert(0 <= n);

?}

2003/2004Introdução à Programação13

factorialDe()

/** Devolve o factorial do inteiro não negativo passado como argumento.    @pre  0 ≤ n.     @post factorialDe = n!. */ int factorialDe(int const n) { assert(0 <= n);

if(n == 0) return 1; else return ?;}

2003/2004Introdução à Programação14

factorialDe()

/** Devolve o factorial do inteiro não negativo passado como argumento.     @pre  0 ≤ n.    @post factorialDe = n!. */ int factorialDe(int const n){ assert(0 <= n);

if(n == 0) return 1; else return n * factorialDe(n - 1);}

2003/2004Introdução à Programação15

Recursividade

Rotina recursiva Corpo invoca a própria rotina Corpo invoca rotinas que invocam a rotina

2003/2004Introdução à Programação16

factorialDe(): Traçado

#include <iostream>

using namespace std;

/** Devolve o factorial do inteiro não negativo passado como argumento. @pre 0 ≤ n. @post factorialDe = n!. */ int factorialDe(int const n) { assert(0 <= n);

if(n == 0) return 1; else return n * factorialDe(n - 1);}

int main() { cout << factorialDe(3) << endl; }

factorialDe()

main()

n: int {frozen}

3

2003/2004Introdução à Programação17

Pilha

Estrutura onde se acumulam coisas de baixo para cima

Acesso directo ao topo

Computador usa pilha para arrumar a casa durante invocação de rotinas

Topoda

pilha

2003/2004Introdução à Programação18

a: int

1

b: int

2

: int

3

somaDe(): Traçado

#include <iostream>

using namespace std;

int somaDe(int const a, int const b) { return a + b; } int main() { soma(1, 2) cout << << endl; }

2003/2004Introdução à Programação19

factorialDe(): Traçado

#include <iostream>

using namespace std;

/** Devolve o factorial do inteiro não negativo passado como argumento. @pre 0 ≤ n. @post factorialDe = n!. */ int factorialDe(int const n) { assert(0 <= n);

if(n == 0 or n == 1) // 1 return 1; // 2 else factorialDe(n – 1) // 3A return n * ; // 3B}

int main() { factorialDe(3) // 4A cout << << endl; // 4B}

2003/2004Introdução à Programação20

retorno a 4B

n: int

3

retorno a 3B

retorno a 3B

n: int

1

retorno a 3B

Traçado

Topo da pilha

retorno a 4B

n: int

3

retorno a 4B

n: int

3

n: int

2

n: int

2

retorno a 3B

retorno a 4B

n: int

3

retorno a 4B

n: int

3

n: int

2

: int

1

: int

2

: int

6

Valor devolvido

O mesmo que {frozen}

2003/2004Introdução à Programação21

A reter…

Pilha Estrutura organizada de baixo para cima Acesso directo ao topo

Computador usa pilha para arrumar a casa durante invocação de rotinas

Pilha termina sempre como começou

Recursividade introduz ineficiências Trabalhos de arrumação da casa usando pilha

• Memória usada• Velocidade de execução

2003/2004Introdução à Programação22

Aula 5: Sumário

Sobrecarga de nomes de rotinas: Noção de assinatura Utilizações

Rotinas recursivas: Problemas Garantia de terminação Aplicações

Mecanismo de invocação de rotinas: Pilha Instâncias locais, parâmetros e valor devolvido Porque, e como, funcionam as rotinas recursivas