Iteração
A iteração é a repetição de um processo. Um aluno que vai à escola repete o processo de ir à escola todos os dias até a formatura. Vamos ao supermercado pelo menos uma ou duas vezes por mês para comprar produtos. Repetimos esse processo todos os meses. Em matemática, uma sequência de Fibonacci também segue as propriedades de repetição de tarefas. Vamos considerar a sequência de Fibonacci onde os primeiros dois números são 0 e 1, todos os outros números são a soma dos dois números anteriores.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Etapas de iteração
A fórmula de Fibonacci pode ser escrita como,
F (n) = F (n - 1) + F (n - 2)
fibonacci (0) = 0
fibonacci (1) = 1
fibonacci (2) = fibonacci (1) + fibonacci (0) = 1 + 0 = 1
fibonacci (3) = fibonacci (2) + fibonacci (1) = 1 + 1 = 2
fibonacci (4) = fibonacci (3) + fibonacci (2) = 2 + 1 = 3
fibonacci (5) = fibonacci (4) + fibonacci (3) = 3 + 2 = 5
fibonacci (6) = fibonacci (5) + fibonacci (4) = 5 + 3 = 8
O algoritmo fornecido a seguir retorna o enésimo número de Fibonacci.
Recursão
Cada vez que obtemos um novo número de Fibonacci (enésimo número), esse enésimo número é na verdade (n - 1) o número quando encontramos (n + 1) o Fibonacci como nosso próximo enésimo Fibonacci. Como vemos as etapas de iteração mencionadas acima: se n = 2, então
Fibonacci (2) = Fibonacci (2 - 1) + Fibonacci (2 - 2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1
Agora, queremos gerar fibonacci (3), que é n = 3.
Fibonacci (3) = Fibonacci (3 - 1) + Fibonacci (3 - 2) = Fibonacci (2) + Fibonacci (1) = 1 + 1 = 2
Isso significa que cada vez que n aumenta o valor da corrente (n - 1) ésimo e (n - 2) ésimo fibonacci também aumenta. Mas é cansativo acompanhar (n - 1) o e (n - 2) o fibonacci para cada n. Que tal escrever um método que chama a si mesmo para repetir a tarefa de iteração por si mesmo?
Um método que chama a si mesmo é denominado método recursivo. Um método recursivo deve ter um caso base em que o programa pare de chamar a si mesmo. Nosso caso base para a série de Fibonacci é fibonacci (0) = 0 e fibonacci (1) = 1. Caso contrário, o método de Fibonacci se autodenomina duas vezes - fibonacci (n - 1) e fibonacci (n - 2). Em seguida, adiciona-os para obter fibonacci (n). Um método recursivo para encontrar o enésimo Fibonacci pode ser escrito como -
Se olharmos com atenção, a recursão segue a propriedade da pilha. Ele resolve subproblemas menores para obter a solução de um problema. Para n> 1, executa a última linha. Portanto, se n = 6, a função chama e adiciona fibonacci (6 - 1) e fibonacci (6 - 2). fibonacci (6 - 1) ou fibonacci (5) chama e adiciona fibonacci (5 - 1) e fibonacci (5 - 2). Essa recursão continua até que 6 atinja seu valor de caso base, que é fibonacci (0) = 0 ou fibonacci (1) = 1. Uma vez que atinge o caso base, ele adiciona dois valores base e sobe até obter o valor de fibonacci ( 6). Abaixo está uma representação em árvore da recursão.
árvore de recursão
Como podemos ver, quão poderosa pode ser uma recursão. Apenas uma única linha de código está formando a árvore acima (última linha do código acima incluindo os casos básicos). A recursão mantém uma pilha e vai mais fundo até chegar ao caso base. Programação dinâmica (DP): a recursão é fácil de entender e codificar, mas pode ser cara em termos de tempo e memória. Dê uma olhada na árvore de recursão abaixo. A subárvore esquerda começando com fib (4) e a subárvore direita começando com fib (4) são exatamente iguais. Eles geram o mesmo resultado que é 3, mas estão fazendo a mesma tarefa duas vezes. Se n for um número grande (exemplo: 500000), a recursão pode tornar um programa muito lento, pois chamaria a mesma subtarefa várias vezes.
recursion Tree-circled
Para evitar este problema, a programação dinâmica pode ser usada. Na programação dinâmica, podemos usar subtarefas previamente resolvidas para resolver tarefas futuras do mesmo tipo. Esta é uma forma de reduzir a tarefa de resolver o problema original. Vamos ter um array fib [] onde armazenamos soluções de subtarefas previamente resolvidas. Já sabemos que fib [0] = 0 e fib [1] = 1. Vamos armazenar esses dois valores. Agora, qual é o valor da fib [2]? Como fib [0] = 0 e fib [1] = 1 já foram armazenados, só temos que dizer fib [2] = fib [1] + fib [0] e isso é tudo. Podemos gerar fib [3], fib [4], fib [5], ……, fib [n] da mesma maneira. As subtarefas resolvidas anteriormente são chamadas para obter a próxima subtarefa até que a tarefa original não seja resolvida, reduzindo assim o cálculo redundante.
