Recursively traversing a deep tree somehow got too deep for me. Converting to iterations does not seem to be obvious. So I decided to play with manually passing continuations. Below is a simple example just came to me. Do you think a macro to provide such transformation (from isEven_R to isEven) would be useful in general?
proc isEven_R(n:int):bool
proc isOdd_R(n:int):bool
proc isOdd_R(n:int):bool =
if n == 1: return true
elif n == 0: return false
else: return isEven_R(n-1)
proc isEven_R(n:int):bool =
if n == 1: return false
elif n == 0: return true
else: return isOdd_R(n-1)
type Ret[A,R] = object
case fin: bool
of false:
prc: proc(a:A):Ret[A,R]
arg: A
of true:
ret: R
template cont[A,R](p,a:untyped):auto =
Ret[A,R](fin:false,prc:p,arg:a)
template retn[A,R](r:R):auto =
Ret[A,R](fin:true,ret:r)
proc isOdd_P(n:int):Ret[int,bool]
proc isEven_P(n:int):Ret[int,bool]
proc isOdd_P(n:int):Ret[int,bool] =
if n == 1: return retn[int,bool](true)
elif n == 0: return retn[int,bool](false)
else: return cont[int,bool](isEven_P,n-1)
proc isEven_P(n:int):Ret[int,bool] =
if n == 1: return retn[int,bool](false)
elif n == 0: return retn[int,bool](true)
else: return cont[int,bool](isOdd_P,n-1)
template apply(f,a):auto =
var r = f(a)
while not r.fin:
r = r.prc r.arg
r.ret
template isEven(a:int):bool = apply(isEven_P,a)
template isOdd(a:int):bool = apply(isOdd_P,a)
let n = 10000
echo "without recursion"
echo isEven n
echo "with recursion"
echo isEven_R n