How come this conversion from recursion to iteration magically works?

Question

Not without trouble, I've been able to convert the following snippet from recursion to iteration.

Recursion:

private static Bin Find(Bin bin, int w, int h)
{
    if (bin.Used)
        return Find(bin.Right, w, h) ?? Find(bin.Down, w, h);

    if (w <= bin.W && h <= bin.H)
        return bin;

    return null;
}

Iteration:

private static Bin Find(Bin bin, int w, int h)
{
    var stack = new Stack<Bin>(new[] {bin});

    while (stack.Any())
    {
        var pop = stack.Pop();

        if (pop.Used)
        {
            stack.Push(pop.Down);
            stack.Push(pop.Right);

            continue;
        }

        if (w <= pop.W && h <= pop.H)
            return pop;
    }

    return null;
}

Now there is something I don't understand, how come it magically works ?

Because when you look out at original implementation:

while bin is used, keep trying on Right bin
else keep trying on Down bin

While on iteration I push both leaves, Right and Down are popped/processed sequentially but it still works.

Question:

Is my code not totally correct but because of the way that data structure is it works anyway ?

Or does my conversion to iteration really match the original recursion?

Reference:

Here's the complete algorithm in case you want to look at it.

using System;
using System.Collections.Generic;
using System.Linq;
using JetBrains.Annotations;

namespace ABCD
{
    public static class BinPacker
    {
        public static void Fit([NotNull] Size[] sizes)
        {
            if (sizes == null)
                throw new ArgumentNullException(nameof(sizes));

            var root = new Bin
            {
                X = 0,
                Y = 0,
                W = sizes.Length > 0 ? sizes[0].W : 0,
                H = sizes.Length > 0 ? sizes[0].H : 0
            };

            var rects = new Rect[sizes.Length];

            for (var i = 0; i < sizes.Length; i++)
            {
                var s = sizes[i];
                var w = s.W;
                var h = s.H;
                var n = Find(root, w, h);
                n = n != null ? Split(n, w, h) : Grow(ref root, w, h);

                rects[i] = new Rect(n.X, n.Y, w, h);
            }
        }

        private static Bin Find(Bin bin, int w, int h)
        {
            if (bin.Used)
                return Find(bin.Right, w, h) ?? Find(bin.Down, w, h);

            if (w <= bin.W && h <= bin.H)
                return bin;

            return null;
        }

        private static Bin Split(Bin bin, int w, int h)
        {
            bin.Used = true;

            bin.Down = new Bin
            {
                X = bin.X,
                Y = bin.Y + h,
                W = bin.W,
                H = bin.H - h
            };

            bin.Right = new Bin
            {
                X = bin.X + w,
                Y = bin.Y,
                W = bin.W - w,
                H = h
            };

            return bin;
        }

        private static Bin Grow([NotNull] ref Bin bin, int w, int h)
        {
            if (bin == null)
                throw new ArgumentNullException(nameof(bin));

            var canGrowR = h <= bin.H;
            var canGrowD = w <= bin.W;
            var letGrowR = canGrowR && bin.H >= bin.W + w;
            var letGrowD = canGrowD && bin.W >= bin.H + h;

            if (letGrowR)
                return GrowRight(ref bin, w, h);

            if (letGrowD)
                return GrowDown(ref bin, w, h);

            if (canGrowR)
                return GrowRight(ref bin, w, h);

            if (canGrowD)
                return GrowDown(ref bin, w, h);

            return null;
        }

        private static Bin GrowDown([NotNull] ref Bin bin, int w, int h)
        {
            if (bin == null)
                throw new ArgumentNullException(nameof(bin));

            bin = new Bin
            {
                X    = 0,
                Y    = 0,
                W    = bin.W,
                H    = bin.H + h,
                Used = true,
                Down = new Bin
                {
                    X = 0,
                    Y = bin.H,
                    W = bin.W,
                    H = h
                },
                Right = bin
            };

            var find = Find(bin, w, h);

            return Split(find, w, h);
        }

        private static Bin GrowRight([NotNull] ref Bin root, int w, int h)
        {
            if (root == null)
                throw new ArgumentNullException(nameof(root));

            root = new Bin
            {
                X    = 0,
                Y    = 0,
                W    = root.W + w,
                H    = root.H,
                Used = true,
                Down = root,
                Right = new Bin
                {
                    X = root.W,
                    Y = 0,
                    W = w,
                    H = root.H
                }
            };

            var node = Find(root, w, h);

            return Split(node, w, h);
        }
    }

    internal sealed class Bin
    {
        public int X { get; set; }

        public int Y { get; set; }

        public int W { get; set; }

        public int H { get; set; }

        public bool Used { get; set; }

        public Bin Down { get; set; }

        public Bin Right { get; set; }

        public override string ToString()
        {
            return $"{nameof(X)}: {X}, {nameof(Y)}: {Y}, {nameof(W)}: {W}, {nameof(H)}: {H}, {nameof(Used)}: {Used}";
        }
    }

    [PublicAPI]
    public struct Size : IEquatable<Size>
    {
        public readonly int W, H;

        public Size(int w, int h)
        {
            W = w;
            H = h;
        }

        public override string ToString()
        {
            return $"{nameof(W)}: {W}, {nameof(H)}: {H}";
        }

        public bool Equals(Size other)
        {
            return W == other.W && H == other.H;
        }

        public override bool Equals(object obj)
        {
            return obj is Size other && Equals(other);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                return (W * 397) ^ H;
            }
        }

        public static bool operator ==(Size left, Size right)
        {
            return left.Equals(right);
        }

        public static bool operator !=(Size left, Size right)
        {
            return !left.Equals(right);
        }
    }

    [PublicAPI]
    public struct Rect : IEquatable<Rect>
    {
        public readonly int X, Y, W, H;

        public Rect(int x, int y, int w, int h)
        {
            X = x;
            Y = y;
            W = w;
            H = h;
        }

        public override string ToString()
        {
            return $"{nameof(X)}: {X}, {nameof(Y)}: {Y}, {nameof(W)}: {W}, {nameof(H)}: {H}";
        }

        public bool Equals(Rect other)
        {
            return X == other.X && Y == other.Y && W == other.W && H == other.H;
        }

        public override bool Equals(object obj)
        {
            return obj is Rect other && Equals(other);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                var hashCode = X;
                hashCode = (hashCode * 397) ^ Y;
                hashCode = (hashCode * 397) ^ W;
                hashCode = (hashCode * 397) ^ H;

                return hashCode;
            }
        }

        public static bool operator ==(Rect left, Rect right)
        {
            return left.Equals(right);
        }

        public static bool operator !=(Rect left, Rect right)
        {
            return !left.Equals(right);
        }
    }
}

MyBug18 · Accepted Answer · 2020-04-01T07:15:32.713

The magic is based on the fact that stack is the data sturcture which implements FILO (First In, Last Out).

Let's look at the recursion. After you look at bin, you move your eye to bin.Right and bin.Down. The thing is, you can't move your eye to bin.Down until you finish your work with bin.Right.

From this fact, let's move on to the stack-way.

First, push the first bin.

bin - bottom

After we look at the popped bin, we push bin.Down and bin.Right. Note that bin.Down is pushed first.

bin.Right - bin.Down - bottom

And again we do the same thing with the popped bin.Right.

bin.Right.Right - bin.Right.Down - bin.Down - bottom

And We figure out that there is nothing to do with bin.Right.Right, so pop again to look at bin.Right.Down... and the same thing goes on.

Down here, you may have figured out. Until you finish the work with bin.Right, bin.Down has never popped. That's the magic.

How come this conversion from recursion to iteration magically works?

1 Answers1