DEV Community 👩‍💻👨‍💻

Cover image for recursion in typescript
oreychandan
oreychandan

Posted on

recursion in typescript

One word, 'trampoline'.

Sometimes you just come across something brilliant and wonder
"why did I not think of that?". Such discoveries humble you but also if you are like me, makes you realize you need to think out of the box next time. "Out of the box" here just means think fresh. Because when you are stuck with a problem, the last thing you need to do is trying to solve it the same way again.

So I am getting deep into functional programming. I am having blast. Been a while since I had so much fun coding. But I had a problem. I cannot do recursive functions. I know how to do them, but typescript complains that the function refers to itself.
Image description
So at first I was like ha, must be a limitation of typescript because you can do this in javascript without any problems right? Ah javascript you got my again, with your smooth talking lies.
Nope, I suddenly realized what the word 'stackoverflow' meant. In brief, when you call a function, that function creates a 'stack'. It is memory where the parameters and some other stuff live until the function finishes execution. But when you call the function recursively the stack just blows up after a number of recursions, causing a runtime error.
screenshot showing the error

I tried a few ways to create a workaround, but none worked in a way I wanted or at all.

But recently when I was not even looking for this I came across a technique called 'trampoline'.

Here's the implementation I found: source
Image description
I made some modifications, because why not XD.
article on trampolines by Benjamin Johnson

I made the modifications because, (nothing against the source, its a great example to explain the concept)

  1. what if the function we are creating returns a function by design? that will break this code.
  2. the usage of it "trampoline(someFunction)", implies you can do this with just about any function, but that is not how it works.

So with my modifications this is how a recursive function is defined, (there might be a better way, but its best I could create right now)
screen shot of my implementation

I already have a couple of changes I might want to do to this, but I am so glad that I came across this concept that I just wanted write down my thoughts in the post. Maybe someone else who never knew this found it through me. That would be my pleasure !

Top comments (1)

Collapse
 
modex98 profile image
Mourad EL CADI

thanks)

🌚 Friends don't let friends browse without dark mode.

Sorry, it's true.