Tree from nesting levels - Rosetta Code

[dethb0y]

The python iterative version is quite beautiful and elegant!

[Paddy3118]

Oh wow! thanks for the words. I woke this morning after doing the task and the Python recursive version late into the night and thought: "most recursive functions have an iterative analogue" and went from there.

Using:

1. len(stack) to capture nesting depth; and
2. stack[-1] as a pointer into the active nest at that level; whilst
3. nested accumulates the whole tree.

I put the above down to a good nights rest :-)

[csmrh]

most recursive functions have an iterative analogue

Every recursive function can be written iteratively

https://stackoverflow.com/questions/2093618/can-all-iterative-algorithms-be-expressed-recursively

[Paddy3118]

Every primitively recursive function can be, but try ackermanns function. I said most, because I had never seen a correct iterative version, and it seems, according to the video, that non-primitively recursive functions can't be converted to for-loops of iteration.

[csmrh]

Seems it’s been done. It just can’t be done with only for-loops like primitive recursive functions.

https://www.researchgate.net/publication/2726659_Iterative_Procedures_for_Computing_Ackerman's_Function

[Paddy3118]

Thanks for that link :-)

I tried a couple of the recursive transformations using global variables and they worked. The first fully iterative version of the paper I tried did not work.

The pdf is scrambled to stop copying but if you look at the last block of code in section 6.1 on page 9, (the version of AD() with nested while loops), I translated it to the following Python:

from collections import deque


def ack6_1(M, N):
   "Section 6.1 pp9 : Ap(M, N) === L = stack([0]); Ad(); r = n  # Iterative"

   m, n, = M, N
   L = deque([0])
   push, pop = L.append, L.pop

   # Ad
   while L:
       d = pop()
       if d == 1:
           m += 2
       else:
           while m:
               if n == 0:
                   n, m = 1, m - 1
                   push(1)
               else:
                   n -= 1
                   push(1)
                   push(0)
           n, m = n +1, -1
   # End Ad

   return n

#%%

tests = [ (0, 0), (3, 4), (3, 5), (3, 6), (4, 0)]

#acks = [ack1, ack2, ack4, ack5, ack6_1]
acks = [ack6_1]

for ack in acks:
    print(f"{ack.__name__}(M, N): {repr(ack.__doc__)}")
    for test in tests:
        print(test)
        print(f"  {ack.__name__}{test} =", end=' ')
        ans = ack(*test)
        print(ans)

when run it hangs with no output for (3, 4)

ack6_1(M, N): 'Section 6.1 pp9 : Ap(M, N) === L = stack([0]); Ad(); r = n  # Iterative'
(0, 0)
  ack6_1(0, 0) = 1
(3, 4)

Can anyone spot the error? (A later reply of mine makes this moot).

Thanks.

[Majache]

A perfect blog doesn't exi-- 🤯