/ put this in your pipe and recur on it!

*** alert: k3 ahead ***

blowing the stack with a recursive function is like stepping on a rusty nail.

"hey, this worked for n=20, why is it exploding with n=30?"

in these cases it would be nice to have a method - a recipe, or at least a (an?) heuristic for concocting an equivalent iterative function.

programmers new to k experience fear and trembling when confronted by the symbolic forms for converge, do, and while (/ and \), and by "programmers new to k" i mean everyone except that guy who documents his code in etruscan.

i spent the better part of this afternoon hunting for an iterative equivalent to my implementation of primitive recursion:

    r:{:[*|z;y z,r[x;y]z-:|1,1_&#z;x z]}

x and y are monadic functions.  r recurs on z whose last element is steadily reduced by 1 (we subtract 1 from z's last element).  we prepend z to the recursion on the reduced z, and apply y to the result.  we apply x to z when *|z goes to zero.

that seems pretty straightforward.  now having described what it's doing in english it should be simple to transcribe it as an iterative function.  but is it?

the best i could do is:

    r:{r:,z;do[*|z;r,:,z-:|1,1_&#z];{y z,x}/[x@*|r;y;|1_ r]}

load the result with ,z.  then do (*|z)-many times: append the reduce-last-element-by-1 of z to r.  after *|z times (when z goes to zero) reduce the {y z,x} function over the initial value x@*|r (apply the function x to the last of r), the function y, and the reverse of the 1-drop of r.  note that f/[x;y;z] doesn't balk because x is the value to modify, y is an atom (a lambda), and z is a list over which we will apply f.

that doesn't seem straightforward at all!

fortunately everything up to the reduction step can be factored out and converted to a shorter and more intelligible scan.  that part:

    r:,z;do[*|z;r,:,z-:|1,1_&#z]
    ----------------------------

does nothing except build the structure which the reduction step will reduce.  so:

    r:{{y z,x}/[x@*|z;y;|1_ z:(*|z){x-|1,1_&#x}\z]}
                        -------------------------

but wait!  that do-scan can be eliminated by a simple array calculation:

    r:{{y z,x}/[x@*|z;y;|1_ z:|(-1_ z),/:!1+*|z,:!0]}
                        ---------------------------