Computação III Professor: Mtr. David Batard Lorenzo

Instituto Superior para as Tecnologias de Informção e Telecomunicação

ISUTIC

Bibliografia da matéria

–Aho, Hopcroft, Ullman. Estructura de Datos y

Algoritmos.

– CORMEN, T. H. et al. Algoritmos: Teoria e Prática; Rio

de Janeiro: Editora Campus, 2002.

– Thomas H. Cormen, Charles E. Leiserson. Introduction

to Algorithms. Second Edition.

–TAMASSIA, R. e GOODRICH, M. T. Estruturas de

Dados e Algoritmos em JAVA; Porto Alegre: Editora

Bookman, 2002.

Objectivo

• Resolver exercícios usando uma abordagem recursiva

Exemplos de conceitos recursivos

Há conceitos que se utilizam a si mesmos para se explicar.

- Um ramo de uma árvore tem ramos…

Algoritmo Recursivo

Há algoritmos que se explicam em termos de si mesmos. Umalgoritmo que se define parcialmente em termos de si mesmos sedenomina recursivo.

(Epígrafe 9 pág. 1 del Katrib)

Algoritmo Recursivo

O método recursivo é um método que chama a si própriodiretamente ou indiretamente, através de outro método.

(Epígrafe 6.12, pág. 286 del “Java ,como programar”/H.M.Deitei

LangLisboa.-4,ed.-PortoAlegre:Bookman,2003) En Portugues

Partes de um Algoritmo RecursivoCaso base:

• Parte mais simples.

• Caso ou casos triviais para os que se conhece umasolução direta.

Parte ou etapa recursiva:

• Parte mais complexa.

• Parte onde se faz alusão à própria definição.

Mais sobre os Algoritmos Recursivos

1.Pode ter mais de um caso base e a parte recursiva podecontar com mais de uma instrução.

2.O caso base actua como condição de terminação darecursividad. Sem a existência ou identificação do caso base arotina chamar-se-ia indefinidamente.

Mais sobre os Algoritmos Recursivos

3.A parte recursiva é a que encarregar-se-á de dividir o problemagrande num mais pequeno até chegar a uma solução direta ousingela que será um dos casos baseie..

Es de suma importancia que la parte recurrente converja a un casobase para lograr la terminación del algoritmo.

Exemplo de Algoritmo RecursivoUm exemplo de função recorrente é a definição dada para ocálculo do factorial de um número.

1. O Factorial de 0 é 1.

2. O Factorial de um n > 0 é

n * Factorial de n-1.

Exemplo de Algoritmo RecursivoA Sucessão de Fibonacci define-se mediante a função derecurrencia.

f0 = 0

f1 = 1

fn = fn-1 + fn-2 (n ≥ 2)

Problema (Factorial)

Execução:

factorial(3) = 3*factorial(2) = 3 * (2 * factorial(1)) = 3*(2*(1*factorial(0))) = 3*2*1= 6.

Constrói-se a solução para n=3 a partir do caso base..

Solução:

public int factorial(int n) {

if(n == 0)

return 1;

return n * factorial(n-1);

}

¿Como funciona um método recursivo?

public static void main(String []args){

int x = 3;

int fac = factorial(x);

}

a)Escreva um método para obter o resultado de um número Nelevado ao M.

b)Adicione os números naturais até chegar a N, recursivamente.

c)Escreva um método para determinar se um número é par demaneira recursiva.

d)Mostre o conteúdo de um Array sem usar for ou while.

Exercicios