estudante

Recursividade
Prof. Tiago Massoni
Prof. Fernando Buarque
Prof. Byron Leite
Engenharia da Computação
Poli - UPE

Funções regulares
• Elementos
–
–
–
–

declaração (inclui parâmetros formais), chamada (inclui argumentos), corpo e retorno 2

Funções regulares

Func A

3

Funções recursivas
• Idênticas às regulares com uma diferença: – Chamada direta ou indireta à mesma função de dentro do seu corpo
– Exemplos a (parâmetros) {
…

a (parâmetros) {
…

b (parâmetros) {
…

a(argumentos);

b(argumentos);

a(argumentos);
}

} // direta

} // indireta

4

Funções recursivas

Func.
Func A

5

Funções definidas por elas mesmas • Uma função pode ter uma definição indireta • Exemplo
– f(0)=0
– f(x)= 2f(x-1)+x2

• Como escreveríamos esta função em
Java?
6

Recursão
• Definição especificada por um processo
• Caso base
• Chamada recursiva

• Exemplo: função fatorial
0! = 1
1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
...
n! = n * (n-1) * (n-2) ... * 1 se n>0 ou ainda n! = n * (n-1)!

7

Recursão x Iteração: fatorial prod =1;
...
for (x=n; x>0; x--) { if(n==0) prod *= x; fact = 1;
}
else { return (prod); fact = n*fat(n-1);
}
return fact;
8

Caso base e terminação
• Caso base: define quando a função recursiva deve parar
– Chamadas resolvidas sem recursão
– Sempre deve haver progresso em direção ao caso base
– Senão, círculo (estouro de pilha)

9

Exercício
• Escrever um programa em Java usando recursão que imprima a série de Fibonacci
0, 1, 1, 2, 3, 5, 8, 13, 21, 34... ou seja fib(0) = 0, fib(1) = 1, fib(2) = 1, ...
i.e. fib(n) = n, se n==0 ou n==1 fib(n) = fib(n-2) + fib(n-1), se n>= 2
10

Classe programa public class Fibonacci {
//metodos estaticos ... public static void main(String[] args){
//codigo que chama os metodos estaticos
...
}
}

11

Fibonacci iterativo public static int fibonacciIterativo(int n){ int soma = n; if (soma >= 2) {