Stack Free Recursion (1995)

Re:Stack Free Recursion (1995) by tromp on Sunday November 09, 2014 @02:43PM (#8580647)

Hanoi is not the best example of a problem calling for recursion, as the following iterative solution shows:

    max = 1 << no_of_discs;
    for (x = 1; x < max; x++)
        printf("move a disc from %d to %d\n", (x&x-1)%3, ((x|x-1)+1)%3);

[ Parent | on HN ]

Re:Stack Free Recursion (1995) by icarot on Monday November 10, 2014 @09:26AM (#8583623)

You're right. The de-facto way to prove an algorithm as stack-free is run it on a register machine, having no stack to begin with. As you suggest, it'd also be optimal to use a problem which calls for deep recursion.

Hence the task, should ye choose to accept, is compute the Ackermann function as an iterative process (i.e, with state variables in the recursion keeping track of which step at the process you are at). The following is the easy, non-iterative process:

(define (A x y) (cond ((= y 0) 0) ((= x 0) (* 2 y)) ((= y 1) 2) (else (A (- x 1) (A x (- y 1))))))

space is O(n) to record past results in one of the two subtrees of this tree recursion at any given time, which must both be evaluated separately, and at separate times if evaluation is deterministic (not concurrent). So if you were to recast it iteratively, you'd hold an immaculate benchmark of an abstrusely deep recursion which you could run on a register machine. I'm not sure if anyone has done this.

[ Parent | on HN ]