[Programming] Proper Tail Recursion - Bypass recursion limit

[FernandoMorea]

My research on how to bypass hp prime's recursion limit, coupled with my studies of lisp and haskell, led me to this solution: saving the continuation of a function in a variable, that will be returned to the user, the user must re-run the result to iterate the process.
To cheat the static analysis of the CAS that triggers the recursion limit, we must also define a fake function that simply calls back the main function.

The function must be tail recursive:
Let's recall what a tail recursive function looks like, let's take the factorial and python as toy language:

Code:


def factorial(n, a):
  if n < 0:
    return 0
  elif n == 0:
    return 1
  elif n == 1:
    return a
  else:
    return factorial(n - 1, n * a)

So now let's go to our HP PRIME:

Code:


#cas
self_fact:= 
cont:= QUOTE(myfact(arg0,arg1));

myfact(x,curr):= 
IF x≤0
THEN curr
ELSE
arg0:=x-1; 
arg1:=x*curr; 
cont:= QUOTE(self_fact);
{'cont',arg1};
END;

#end

Another example could be the algorith for Polynomial long division

Code:


#cas
long(a,b):=
BEGIN
LOCAL t;
t:= [a(1)/b(1), a-(a(1)/b(1))*b];
tempa:= tail(t(2));
tempb:= b;
cont:=QUOTE(self_long);
{'cont', t};
END;

self_long:=
cont:=QUOTE(long(tempa,tempb));
#end

[FernandoMorea]

To test the code try with:

myfact(10,1)
long({1,2,3},{4,5,6})

To continue to run the result you can either copy the last result from the top with the arrow key and run it with enter, or you can do:
eval(Ans)

- Or, better, you can write:
cont
After that, you can spam the enter key to run the continuation till the end of the algorithm (in the case of the factorial you have exactly n iteration, so if you wrote myfact(100,1) you should spam the enter key for 100 times, still not practical but it works).

[FernandoMorea]