Explore alternatives to recursion

[ok-ryoko]

Code of conduct

• I have read and agree to the community’s code of conduct.

Scope

• HeadNode.countBelow
• HeadNode.removeAbove
• HeadNode.removeBelow
• DataNode.removeAfterZ
• MultiRing.remove

Implementation

The implementation of every named method uses multiple recursion.

For a ring containing n subrings, where n is an arbitrarily large positive integer, HeadNode.countBelow, HeadNode.removeBelow and MultiRing.remove call themselves n times. DataNode.removeAfterZ calls HeadNode.removeBelow zero or more times; HeadNode.removeAbove calls DataNode.removeAfterZ exactly once. Because n can be made arbitrarily large, i.e., greater than 2, every named method's implementation uses multiple recursion.

Some implementations also use indirect recursion.

DataNode.removeAfterZ calls HeadNode.removeAbove exactly once. The two methods call one another, so their implementations use indirect recursion.

I propose the exploration of implementations that use either direct, linear and (preferably) tail recursion or no recursion at all.

Value proposition

Recursive functions can be shorter and more readable than their non-recursive counterparts at the expense of greater memory consumption. The purpose of this work is to evaluate this statement in the context of this project.

Because multirings can be made arbitrarily tall and wide, and recursion takes place when entering or exiting any ring, there is the possibility of unsafe recursion (stack overflow). A non-recursive solution shouldn't pose this risk.

Suppose N is the number of rings in a multiring. If no recursive method call can be optimized, then every such call will consume more memory. Because recursion takes place only at ring boundaries, recursive method implementations are expected to be less efficient for larger N. By designing and implementing benchmarks, we could demonstrate whether a non-recursive implementation erases this performance asymmetry.

Finally, if we were to use non-recursive implementations exclusively, then all method implementations in multiring.zig would follow a consistent implementation style.

Supporting information

If either this proposal is rejected or the strongest candidate implementation uses a simpler form of recursion, then this repository should take into account the accepted implementation of a solution to ziglang/zig#1006 (safe recursion), the closure of said issue notwithstanding.

[ok-ryoko]

I achieved a recursion-free implementation of each named method in commit a812375 by introducing HeadNode.stepAboveUntilHead and DataNode.stepUntilHeadZ, two step functions that support early termination at any head node of our choice.

The use of multiple and indirect recursion in the previous iteration was particularly detrimental to readability. The recursion-free variants are easier to follow and consistent with the imperative style of the remainder of the module. There’s no longer a risk of stack overflow, which we might otherwise have encountered in a dense multiring (a multiring in which there is a subring at every data node).

Unfortunately, we can’t compare the recursive and non-recursive implementations on the basis of complexity because we don’t have a way to establish complexity to some chosen confidence level from data. This will be the topic of future work.