Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
JSExperience 7masters - Recursion & Trampolines
Search
Ana Luiza Portello
July 05, 2018
Programming
1
370
JSExperience 7masters - Recursion & Trampolines
Ana Luiza Portello
July 05, 2018
Tweet
Share
More Decks by Ana Luiza Portello
See All by Ana Luiza Portello
FRONTIN | Elas Programam - Programação Funcional no Front-end
anabastos
0
94
Workshop JSFP - SEMCOMP 2021
anabastos
0
280
Clojure é um Java melhor que Java - Codecon 2021
anabastos
0
150
Clojure 101 - Criciuma Dev
anabastos
0
320
TDC POA - GraphQL
anabastos
1
270
TDC Porto Alegre 2019 - JS Funcional com Ramda
anabastos
0
240
BackEndSP - GraphQL
anabastos
0
230
Git & Github - RLadies
anabastos
1
240
Programaria Summit - Performance FrontEnd
anabastos
1
220
Other Decks in Programming
See All in Programming
Amazon RDS 向けに提供されている MCP Server と仕組みを調べてみた/jawsug-okayama-2025-aurora-mcp
takahashiikki
1
110
時間軸から考えるTerraformを使う理由と留意点
fufuhu
16
4.8k
知っているようで知らない"rails new"の世界 / The World of "rails new" You Think You Know but Don't
luccafort
PRO
1
150
Kiroで始めるAI-DLC
kaonash
2
590
2025 年のコーディングエージェントの現在地とエンジニアの仕事の変化について
azukiazusa1
24
12k
Ruby×iOSアプリ開発 ~共に歩んだエコシステムの物語~
temoki
0
310
Ruby Parser progress report 2025
yui_knk
1
440
開発チーム・開発組織の設計改善スキルの向上
masuda220
PRO
20
11k
機能追加とリーダー業務の類似性
rinchoku
2
1.3k
AI Coding Agentのセキュリティリスク:PRの自己承認とメルカリの対策
s3h
0
220
testingを眺める
matumoto
1
140
旅行プランAIエージェント開発の裏側
ippo012
2
910
Featured
See All Featured
Keith and Marios Guide to Fast Websites
keithpitt
411
22k
How GitHub (no longer) Works
holman
315
140k
ピンチをチャンスに:未来をつくるプロダクトロードマップ #pmconf2020
aki_iinuma
126
53k
Being A Developer After 40
akosma
90
590k
Code Review Best Practice
trishagee
70
19k
Rails Girls Zürich Keynote
gr2m
95
14k
Mobile First: as difficult as doing things right
swwweet
224
9.9k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
333
22k
Exploring the Power of Turbo Streams & Action Cable | RailsConf2023
kevinliebholz
34
6k
Imperfection Machines: The Place of Print at Facebook
scottboms
268
13k
The Cost Of JavaScript in 2023
addyosmani
53
8.9k
We Have a Design System, Now What?
morganepeng
53
7.8k
Transcript
ANA LUIZA BASTOS github.com/anabastos @naluhh @anapbastos Fullstack Developer na Quanto
e cientista da computação na PUC-SP anabastos.me
JSLADIES fb.com/jsladiesbr twitter.com/jsladiessp meetup.com/JsLadies-BR/ LAMBDA.IO t.me/lambdastudygroup github.com/lambda-study-group/ meetup.com/Lambda-I-O-Sampa- Meetup/
VISÃO GERAL SOBRE RECURSÃO & TRAMPOLINES
VAMOS FALAR SOBRE RECURSÃO
Recursão é quando uma função chama a si mesma até
uma condição parar o loop.
λ Programação Funcional
Fatorial 1! = 1 3! = 1 * 2 *
3 = 6
const iterativeFactorial = (n) => { let i let contador
= 0 for (i = 1; i <= n; i++) { contador *= i } return contador }
1. Qual parte do código é recursiva 2. Condição de
saída
const fac = (n) => { if (n == 0)
{ return 1 } return n * fac(n - 1) }
• EXPRESSIVO • PURO / EVITANDO MUDANÇA DE ESTADO(CONTADOR) •
IMUTABILIDADE DE DADOS • DECLARATIVO • IDEMPOTENCIA
JS é single threaded e orientado a stack
None
GC fac(3) GC fac(2) fac(3) GC fac(1) fac(2) fac(3) GC
fac(0) fac(1) fac(2) fac(3) GC call call call call
GC fac(3) GC fac(2) fac(3) GC fac(1) fac(2) fac(3) GC
fac(0) fac(1) fac(2) fac(3) GC 1 1* 1 = 1 1 * 2 = 2 2 * 3 = 6
GC fac(9999) GC fac(9998) fac(9999) GC fac(9997) fac(9998) fac(9999) GC
oh no ... fac(9998) fac(9999) GC StackOverFlow :(
Cruza os dedos? Senta e chora?
TAIL CALL OPTIMIZATION (TCO)
Truque antigo
GC fac(3) GC fac(2) fac(3) GC fac(1) fac(2) fac(3) GC
fac(0) fac(1) fac(2) fac(3) GC call call call call
TCO faz com que a gente evite explodir o stack
quando fazemos chamadas recursivas
PROPER TAIL CALLS (PTC)
Possibilita que sua função recursiva seja otimizada pela engine.
RECURSÃO EM CAUDA (TAIL CALL)
//Não é tail call :( const fac = (n) =>
n == 0 ? 1 : n * fac(n - 1)
A última coisa a ser feita na função é o
retorno da própria função.
Acumulador
const tailRecursiveFac = (n, acc = 1) => { return
n == 0 ? acc : tailRecursiveFac(n - 1, acc * n) }
ES6 http://www.ecma-international.org/ecma-262/6.0/#sec-tail-position- calls
None
Além disso existem casos de algoritmos que precisam de mais
de duas chamadas recursivas(multiple recursion) e não tem como colocar tudo no final
COMO LIDAR COM ISSO?
CONTINUATION PASSING STYLE (CPS)
Um estilo de programação em que o controle é passado
explicitamente em forma de continuação
Continuação é uma parte de código que ainda vai ser
executada em algum ponto do programa Callbacks por exemplo são continuations
Continuação não chama a si mesma, ela só expressa um
fluxo de computação onde os resultados fluem em uma direção. Aplicar continuações não é chamar funções é passar o controle do resultado.
LAZY EVALUATION
CALL-BY-NEED
> (1 + 3) * 2 8 > const expression
= () => (1 + 3) * 2 > expression() 8
Ou seja, o programa espera receber os dados antes de
continuar.
E daí?
CPS elimina a necessidade de um call stack pois os
valores estarão dentro da continuation sendo executada .
Acumulador para uma continuação
IDENTITY FUNCTION
const id = x => x
• O último parâmetro da função é sempre a continuation.
• Todas as funções precisam acabar chamando sua continuação com o resultado da execução da função.
const cpsFac = (n, con) => { return n ==
0 ? con(1) : cpsFac(n - 1, y => con(n + y)) } cpsFac(3, id) //6
TRAMPOLINES
Técnica stack safe para fazer chamadas tail-recursive em linguagens orientadas
a stack
Um trampoline é um loop que iterativamente invoca funções que
retornam thunks (continuation-passing style)
THUNKS
Função que encapsula outra função com os parâmetros que para
quando a execução dessa função for necessária.
function thunk(fn, args) { return fn(...args) }
Ao invés de chamar a tail call diretamente, cada método
retorna a chamada para um thunk para o trampolim chamar.
const trampoline = (thunk) => { while(thunk instanceof Function){ thunk
= thunk() } return thunk }
• É um loop que chama funções repetidamente • Cada
função é chamada de thunk. • O trampolim nunca chama mais de um thunk • É como se quebrasse o programa em pequenos thunks que saltam pra fora do trampolim, assim o stack não cresce.
const trampolineFac = (n) { const fac = (n, ac
= 1) => { return n == 0 ? ac : thunk(fac, n - 1, ac * n) } return trampoline(thunk(fac, n, 1)) }
GC fac(3) GC call GC fac(2) GC GC bounce bounce
:(
Trade off por stack safety Trocamos o trabalho de criar
stack frames com o de criar binding de funções.
Em muitos casos o trade-off de overhead por expressividade vale
a pena
Trampolines são mais apropriadas para funções complexas em que não
existem soluções iterativas e não conflitam com outras técnicas de mediar controle de fluxo(Promises).
• Kyle Simpson. Functional Light Programming. Cap 8. - github.com/getify/Functional-Light-JS
• Functional Programming Jargon - github.com/hemanth/functional-programming-jarg on • Structure and Interpretation of Computer Programs - Javascript Adaptation
• Compatibilidade TCO - kangax.github.io/compat-table/es6/#test-proper_tail_c alls_ • Yoyojs - npmjs.com/package/yoyojs
• Ramda Memoisation - ramdajs.com/docs/#memoize
t.me/lambdastudygroup github.com/lambda-study-group
OBRIGADA :) https://speakerdeck.com/anabastos