Aula 5
Sobrecarga de nomes de rotinas
Rotinas recursivas
Invocação de rotinas
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;
}
2
Introdução à Programação
2003/2004
Assinatura de uma rotina

Assinatura de uma rotina:



3
Nome
Lista dos tipos dos parâmetros
Não pode existir mais do que uma rotina com a
mesma assinatura
Introdução à Programação
2003/2004
quadradoDe():
assinaturas e invocações

Assinaturas




Invocações



4
quadradoDe, int
quadradoDe, double
quadradoDe, long
cout << quadradoDe(10) << endl;
// int
cout << quadradoDe(10.0) << endl; // double
cout << quadradoDe(10L) << endl; // long
Introdução à Programação
2003/2004
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;
}
5
Introdução à Programação
2003/2004
somaDe():
assinaturas e invocações

Assinaturas:





Invocações:




6
somaDe
somaDe, int
somaDe, int, int
somaDe, int, int, int
cout
cout
cout
cout
<<
<<
<<
<<
somaDe() << endl;
somaDe(1) << endl;
somaDe(1, 2) << endl;
somaDe(3, 2, 1) << endl;
Introdução à Programação
2003/2004
somaDe(): parâmetros com
argumentos por omissão
int somaDe(int
int
int
{
return a +
}
7
const a = 0,
const b = 0,
const c = 0)
b + c;
Introdução à Programação
2003/2004
Factorial

n! = n  n - 1  ...  1 se 0 < n
n! = 1 se n = 0
n

n! = ∏ i
i=1

8
n! = (P i : 1 ≤ i ≤ n : i )
Introdução à Programação
2003/2004
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?


9
0! = 0  (-1)! = 0 ???????
Introdução à Programação
2003/2004
Definição do factorial

Matematicamente de forma recorrente
n! = n  (n - 1)! se 0 < n
n! = 1 se n = 0

Em C++
? factorialDe( ? )
{
?
}
10
Introdução à Programação
2003/2004
factorialDe()
/** Devolve o factorial do inteiro não negativo
passado como argumento.
@pre 0 ≤ n.
@post factorialDe = n!. */
? factorialDe( ? )
{
assert( ? );
?
}
11
Introdução à Programação
2003/2004
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);
?
}
12
Introdução à Programação
2003/2004
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 ?;
}
13
Introdução à Programação
2003/2004
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);
}
14
Introdução à Programação
2003/2004
Recursividade

Rotina recursiva


15
Corpo invoca a própria rotina
Corpo invoca rotinas que invocam a rotina
Introdução à Programação
2003/2004
factorialDe(): Traçado
#include <iostream>
factorialDe()
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);
n: int {frozen}
3
main()
}
int main()
{
cout << factorialDe(3) << endl;
}
16
Introdução à Programação
2003/2004
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
17
Introdução à Programação
Topo
da
pilha
2003/2004
somaDe(): Traçado
#include <iostream>
using namespace std;
int somaDe(int const a, int const b)
{
return a + b;
}
b: int
2
a: int
int main()
{
1
soma(1, 2)
cout <<
<< endl;
: int
3
}
18
Introdução à Programação
2003/2004
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)
return 1;
else
factorialDe(n – 1)
return n *
;
// 1
// 2
// 3A
// 3B
}
int main()
{
factorialDe(3)
cout <<
<< endl;
// 4A
// 4B
}
19
Introdução à Programação
2003/2004
Traçado
n: int
1
Topo da
pilha
Valor
devolvido
: int
1
O mesmo que
{frozen}
retorno a
3B
n: int
n: int
n: int
2
2
2
retorno a
3B
retorno a
3B
retorno a
3B
n: int
n: int
n: int
n: int
n: int
: int
3
3
3
3
3
6
retorno a
4B
retorno a
4B
retorno a
4B
retorno a
4B
retorno a
4B
20
Introdução à Programação
: int
2
2003/2004
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
21
Introdução à Programação
2003/2004
Aula 5: Sumário

Sobrecarga de nomes de rotinas:



Rotinas recursivas:




Problemas
Garantia de terminação
Aplicações
Mecanismo de invocação de rotinas:



22
Noção de assinatura
Utilizações
Pilha
Instâncias locais, parâmetros e valor devolvido
Porque, e como, funcionam as rotinas recursivas
Introdução à Programação
2003/2004