[Programming] Proper Tail Recursion - Bypass recursion limit

[Programming] Proper Tail Recursion - Bypass recursion limit - Printable Version

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: HP Prime (/forum-5.html)
+--- Thread: [Programming] Proper Tail Recursion - Bypass recursion limit (/thread-19724.html)

[Programming] Proper Tail Recursion - Bypass recursion limit - FernandoMorea - 03-27-2023 08:37 PM

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

RE: [Programming] Proper Tail Recursion - Bypass recursion limit - FernandoMorea - 03-28-2023 06:18 AM

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).

RE: [Programming] Proper Tail Recursion - Bypass recursion limit - FernandoMorea - 03-28-2023 07:27 AM

[Image: myfact.png]