2020-06-16 20:54:20
Processo linear iterativo / tail call recursion by @Foxx3r
O processo linear iterativo se difere do processo linear recursivo, no linear iterativo, temos um acumulador, no processo linear recursivo, a gente não tem um acumulador, então para a gente chegar no valor, precisamos desencapsular toda a função (o que faz ela crescer, tanto em tamanho quanto complexidade de algoritmo/tempo), um exemplo de como é feito o cálculo de baixo dos panos do processo linear recursivo em fatorial:
(factorial 6)
(6 * (factorial 5))
(6 * (5 * (factorial 4)))
(6 * (5 * (4 * (factorial 3))))
(6 * (5 * (4 * (3 * (factorial 2)))))
(6 * (5 * (4 * (3 * (2 * (factorial 1))))))
(6 * (5 * (4 * (3 * (2 * 1)))))
(6 * (5 * (4 * (3 * 2))))
(6 * (5 * (4 * 6)))
(6 * (5 * 24))
(6 * 120)
720
Agora vamos ver como é por baixo dos panos o processo linear iterativo:
(factorial 6)
(fact-iter 1 1 6)
(fact-iter 1 2 6)
(fact-iter 2 3 6)
(fact-iter 6 4 6)
(fact-iter 24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
Agora vamos ver o código:
def factorial(n):
if n == 1:
return 1
else:
return fact(n - 1) * n
def factorial2(n):
def fact_iter(product, accumulator):
if product == 1:
return accumulator
else:
return fact_iter(product - 1, accumulator * product)
return fact_iter(n, 1)
A diferença do primeiro pro segundo, é que o primeiro, depois de uma certa quantidade, ele causa stack overflow ou coisa pior na memória
O segundo nunca cresce, sempre permanece do mesmo, e como é tail recursion... O compilador pode fazer uma otimização na memória chamado de Tail Call Optimization (TCO), aonde a cada iteração, ele consegue limpar a memória e assim ela nunca vai se corromper... também, ele trata isso quase como se fosse um loop
Conseguiram perceber como faz?
1:
n - 1
2:
product - 1
1:
return 1
2:
return accumulator
1:
fact(...) * n
2:
accumulator * product
Agora prestem atenção:
def fibonacci(n):
if (n == 1 or n == 0):
return 1
else:
return fibonacci (n - 1) + fibonacci (n - 2)
def fibonacci2(n):
def fib_iter(n, current, previous):
if (n <= 0):
return current
else:
return fib_iter(n - 1, current + previous, current)
return fib_iter(n, 1, 0)
por baixo:
fibonacci 3
fibonacci 2 + fibonacci 1
fibonacci 1 + fibonacci 0 + fibonacci 1
1 + fibonacci 0 + fibonacci 1
1 + 1 + fibonacci 1
1 + 1 + 1
2 + 1
3
fibonacci2 3
fib_iter 3 1 0
fib_iter 2 1 1
fib_iter 1 2 1
fib_iter 0 3 2
3
Aonde current é o quanto de iterações que o programa já rodou, e o previous é o número anterior a essa iteração. a pergunta que vocês devem estar se perguntando agora é:
Por que temos um current e previous? Porque não é assim em fatorial
Simples, porque a gente só precisa dos dois números anteriores na fibonacci:
fib(n - 1) + fib(n - 2)
Precisamos de um número anterior e de um anterior a esse.
Então a cada iteração, dizemos que:
current += previous
previous = cur
Neste código, o acumulador é o current.
Para você saber qual é o acumulador, você simplesmente vê qual está sendo retornado, um exemplo:
fib 3
fib 3 1 0
fib 2 1 1
fib 1 2 1
fib 0 3 2
3
Deu 3, porque o segundo parâmetro é o acumulador. Iniciamos com fib(n, 1, 0), depois previous vira o valor do current (1), e temos um n - 1
Depois disso, é realizado um n - 1 novamente, o que o faz virar 1, e temos cur + prev que dá 2, e prev vira cur, que dá 1
Depois, temos n - 1 que vira 0, e cur + prev (2 + 1) dá 3, e prev vira cur, que dá 2. Agora aqui, ele só retorna 3. Não precisa desencapsular nem nada, só retornar o valor que foi incrementado durante todo o processo.
1.7K viewsFoxxer λ (Estoicist), 17:54
C
