For the sake of completeness, I finally did manage to rewrite the recursive function into tail-recursive one using CPS.
Solution2
contains the recursive function,
Solution3
contains the tail-recursive function without using CPS which I had to rethink the whole procedure, and
Solution4
contains the tail-recursive function using CPS, converted from `Solution2`'s recursive one.
It was quite a brain twister for me, and I’m still not so confident if I’d be able to do this for other pieces of codes in general, but I think I did learn a bit.
One question arose:
Does the tail-recursive function converted with CPS from original recursive function always have the same space complexity, just that the space it occupies is not the stack space anymore? Or am I wrong about it?
If there are any comments, I’d be happy to hear.
