Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Resolvendo problemas clássicos com recursão (TD...

Resolvendo problemas clássicos com recursão (TDC POA 2016)

Para quem é novo em programação funcional, é comum ficar confuso quanto ao uso real da recursão. Vamos entender como podemos resolver problemas do mundo real aplicando essa técnica e comparando com o paradigma clássico assertivo imperativo.

Guilherme Baptista

October 06, 2016
Tweet

More Decks by Guilherme Baptista

Other Decks in Programming

Transcript

  1. ?

  2. 1 + count(["B", "C", "D"]) 1 + 1 + count(["D",

    "D"]) 1 + 1 + 1 + count(["D"]) 1 + 1 + 1 + 1 + count([]) 1 + 1 + 1 + 1 + 0 4
  3. 1 + sum([2, 2, 2]) 1 + 2 + sum([2,

    2]) 1 + 2 + 2 + sum([2]) 1 + 2 + 2 + 2 + sum([]) 1 + 2 + 2 + 2 + 0 7 s
  4. ["A"] ++ as(2, 1) ["A"] ++ ["A"] ++ as(2, 2)

    ["A"] ++ ["A"] ++ [] ["A", "A"]
  5. fibonacci(4) fibonacci(4 - 1) + fibonacci(4 - 2) fibonacci(3) +

    fibonacci(2) fibonacci(3 - 1) + fibonacci(3 - 2) + fibonacci(2 - 1) + fibonacci(2 - 2) fibonacci(2) + fibonacci(1) + fibonacci(1) + fibonacci(0) fibonacci(2 – 1) + fibonacci(2 - 2) + 1 + 1 + 0 fibonacci(1) + fibonacci(0) + 1 + 1 + 0 1 + 0 + 1 + 1 + 0 = 3
  6. Tail Call Optimization 1 + count(["B", "C", "D"]) 1 +

    1 + count(["D", "D"]) 1 + 1 + 1 + counts(["D"]) 1 + 1 + 1 + 1 + count([]) 1 + 1 + 1 + 1 + 0 4
  7. Tail Call Optimization 1 + count(["B", "C", "D"]) 1 +

    count(["C", "D"]) 1 + count(["D"]) 1 + count([]) 0 Tamanho do seu Stack
  8. Tail Call Optimization 1 + count(["B", "C", "D"]) 1 +

    count(["C", "D"]) 1 + count(["D"]) 1 + count([]) 0 Stack Overflow
  9. Tail Call Optimization count("A", "B", "C", "D"], 0) count("B", "C",

    "D"], 1) count("C", "D"], 2) count("D"], 3) count([]], 4) 4 Tamanho do seu Stack s