Menu
Suppose in C++ you're doing too many recursive calls on a recursive function and getting a stack overflow error.
How would you rewrite this in a continuation-passing style to avoid the stack overflow?
I'm having a slight difficulty picturing this in C++.
353
Continuation passing style makes the control flow of programs more explicit as every procedure has the power to change the execution of the remainder of the program, contrast this to the traditional model in which procedures have no control over the behavior of the program once they return to their caller.
Continuation-Passing-Style, Tail Recursion, and Efficiency is not tail recursive, because the recursive call fact(n-1) is not the last thing the function does before returning. Instead, the function waits for the result of the recursive call, then multiples that by the value of n.
A continuation is a callback function k that represents the current state of the program's execution. More precisely, the continuation k is a function of one argument, namely the value that has been computed so far, that returns the final value of the computation after the rest of the program has run to completion.
In computer science, a continuation is an abstract representation of the control state of a computer program.
Well that's a rather open ended question, but Eric Lippert wrote a (well two actually) rather long series about exactly this topic. Not exactly the right language, but it should be rather helpful still and give the general idea.
Though implementing CPS in C++ seems like a lot of work just to fix a single recursive function, when you can just use some algorithm to make the function iterative with a queue (you still use basically the same amount of data, but the heap is far less restricted).
50
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
