<haakonn>
(hm, sorry about the charset problems there)
<avlondono>
I think you'll have to explain how are a and b calculated.
<haakonn>
they're just an arbitrary function of x (e.g., x + 1)
<avlondono>
x + 1? is that an example?
<haakonn>
not to say they are necessarily equal :) yes, it's an example, my question is general
<avlondono>
do you realize that for x + 1 it will never stop?
<haakonn>
granted, there is no base case, but if we pretend there is ...
<avlondono>
obviously it means there is no general answer for this question.
<avlondono>
some cases could be solved using dynamic programming.
<haakonn>
i see
<pango>
it could be rewritten in continuation passing style to avoid using the stack... but can that be called tail recursive ?
cjohnson has joined #ocaml
<Riastradh>
No, pango. That still accumulates a stack. The only difference lies in where the stack is stored.
<pango>
Riastradh: yes. And same thing if he manage its own "stack" with a list, or whatever
<Riastradh>
Whether or not it can be made tail-recursive depends on the algorithm.
<Riastradh>
There is no general transformation to make algorithms tail-recursive.
<haakonn>
so there is a class of algorithms which cannot be made tail-recursive. but there is no general properties on these that inhibits tail-recursion?
<Riastradh>
Given that we know nothing about the algorithm, I can't say.
<Riastradh>
If you're having trouble with stack overflows, you could just manage your own heap-allocated stack (in the form of a list or CPS)
<haakonn>
CPS?
<Riastradh>
Continuation-passing style.
<haakonn>
ah, right
<monochrom>
If a problem provably requires linear space, there is no work around. All you can do is to trade stack for heap or vice versa.
<monochrom>
For this reason I find some oppositions to recursion to be hypocritic.
<Riastradh>
Aversion to recursion is absursion.
<monochrom>
I actually know a general way to turn recursion into iteration. Use a virtual machine / interpreter / operational semantics.
<Riastradh>
That just adds an interpretive overhead. It doesn't modify the space requirements of the algorithm.
<monochrom>
Right.
tonio has left #ocaml []
_JusSx__ has quit ["leaving"]
apfel has joined #ocaml
drewr has quit ["ERC Version 5.0 $Revision: 1.725 $ (IRC client for Emacs)"]
demitar_ has joined #ocaml
demitar_ has quit [Client Quit]
cjohnson has quit [""The only difference between suicide and martyrdom is press coverage""]
Nutssh has joined #ocaml
mlh has joined #ocaml
zzorn_ has joined #ocaml
zzorn_ has quit ["They are coming to take me away ha ha"]
humasect has quit [Read error: 60 (Operation timed out)]
CosmicRay has quit ["Client exiting"]
apfel has quit ["Just died"]
Nutssh has left #ocaml []
pango has quit ["Client exiting"]
pango has joined #ocaml
smkl has quit [Read error: 110 (Connection timed out)]