Recursividade - Implementação

Recursividade e árvores

---

Não estamos mais lidando com estruturas lineares

Estruturas totalmente não-lineares

Sem desenho pré-definido

Recursividade não é um conteúdo pensado para ser trabalhado em Estruturas de Dados. No entanto, para implementar as árvores, vamos utilizar recursividade. Poderia utilizar métodos interativos, contudo, a complexibilidade seria muito maior.

Recursividade. é uma outra forma de se obter repetição, que ocorre quando uma função chama a si mesma.

É útil na implementação de definições indutivas como fatorial, fibonacci e ordenação.

Além de ser útil para manipular estruturas de dados recursivas como listas ligadas, pilhas e árvores.

Costumo falar de recursividade, não invocando necessariamente elementos de estrutura, mas sim alguns conceitos de matemática, para um melhor entendimento da sua aplicabilidade.

Função Fatorial

---

Para demonstrar recurção, começa-se com um exemplo simples que computa o valor da função fatorial.

O fatorial de um inteiro positivo n, denotado n!, é definido como sendo o produto dos inteiros de 1 até n. Se n=0, então n! é 1 por convenção. Agora, se n!=3, vou dizer que n!=3*2*1

Cada método criado em Java, cria um empilhamento de instruções, denominado pilha de execução.

Vai empilhando essas execuções, até chegar no ponto de parada e ressolver, e desempilha na medida que for resolvendo.

Fatorial

Fibonacci

Ponto de parada. sem ele a execução é eterna, como na perspectiva computacional trabalhamos com recursos finitos, o fim será quando estourar a pilha de execução e parar a recurção.

PS.: Por definição matemática, podiamos dizer que tende ao infinito. 

Daí teremos contato com mais uma exceção que fará parte de nossas vidas.Até então, começamos trabalhando com:

Listas Sequênciais

• ArrayIndexOutOfBoundsException

Listas Encadeadas

• NullPointerException

Árvores Binárias

• NullPointerException

• StackOverflowException

StackOverflowException. é o estouro físico da pilha de execução.

Recursividade

---

• Não é um conteúdo de Estrutura de Dados
• Bastante utilizada
• Métodos recursivos não são exclusividade da programação, a matemática tem bastante
• Custo computacional agregado
• Saber escolher bem quando utilizar, é muito importante
• Exceção mais comum de se ver trabalhando com ela é StackOverflow
• Vamos descobrir que pilha é essa que estoura, e como isso acontece
• A medida que essa pilha for crescendo temos um custo computacional e de memória

Como identificar um método recursivo?

Quando o método é invocado dentro dele mesmo.

Implementação do Fatorial

---

Já sabemos que vamos chamar o próprio fatorial dentro desse método.

Quando trabalhamos com recursividade, temos que definir o caso base ou o ponto de parada.

Quando o valor em questão for 1, retorna 1. Se for 0 retorna 1, porque qualquer número multiplicado por 0 é 0, então, daria problema no nosso fatorial.

Caso Base

if(valor <= 1) {//se for 1 ou menor, retorna 1

    return 1;

}

Quando trabalhamos com programação, as instruções são empilhadas.Cada invocação de método, é um elemento a mais na pilha de execução.Cada escopo novo que se abre de chaves, ele vai empilhando mais uma instrução pra ir resolvendo.

A medida que ele resolve desempilha e para no ponto em que ele tinha chamado aquela instrução que desempilhou.

É assim que funciona toda a lógica de execução, em sistemas operacionais modernos.Em SO, muito da lógica de execução é baseada na premissa de pilha de execução.