successive stack configurations will then be The corresponding equalities are Remarks On any given input the TRSs presented so far converge in the same number of steps. They also use the same reduction rules (in this comparison the rules r1, r2, r3 are considered "the same as" the rules r4, r5, r6/r7 respectively). For example, the reduction of converges in 14 steps: 6 × r1, 3 × r2, 5 × r3. The reduction of converges in the same 14 steps: 6 × r4, 3 × r5, 5 × r6/r7. The TRSs differ in the order in which the reduction rules are applied. When is computed following the rules {r4, r5, r6}, the maximum length of the stack stays below . When reduction rule r7 is used instead of rule r6, the maximum length of the stack is only . The length of the stack reflects the recursion depth. As the reduction according to the rules {r4, r5, r7} involves a smaller maximum depth of recursion, this computation is more efficient in that respect. TRS, based on hyperoperators As — or — showed explicitly, the Ackermann function can be expressed in terms of the hyperoperation sequence: or, after removal of the constant 2 from the parameter list, in terms of Buck's function Buck's function , a variant of Ackermann function by itself, can be computed with the following reduction rules: Instead of rule b6 one can define the rule To compute the Ackermann function it suffices to add three reduction rules These rules take care of the base case A(0,n), the alignment (n+3) and the fudge (-3). Example Compute The matching equalities are when the TRS with the reduction rule is applied: when the TRS with the reduction rule is applied: Remarks The computation of according to the rules {b1 - b5, b6, r8 - r10} is deeply recursive. The maximum depth of nested s is . The culprit is the order in which iteration is executed: . The first disappears only after the whole sequence is unfolded. The computation according to the rules {b1 - b5, b7, r8 - r10} is more efficient in that respect. The iteration simulates the repeated loop over a block of code. The nesting is limited to , one recursion level per iterated function. showed this correspondence. These considerations concern the recursion depth only. Either way of iterating leads to the same number of reduction