/// <summary>
/// Recursively converts the stack to an array of its elements (bottom to top), restoring the stack.
/// </summary>
public static T[] ToArray2<T>(this Stack<T> stack)
{
    if (stack.IsEmpty())
        return Array.Empty<T>();

    // Pop the top element
    T top = stack.Pop();
    // Recursively get array of remaining elements
    T[] rest = stack.ToArray2();
    // Restore the popped element
    stack.Push(top);

    // Combine rest and top into a new array
    T[] result = new T[rest.Length + 1];
    for (int i = 1; i <= rest.Length; i++)
        result[i] = rest[i - 1];
    result[0] = top;

    return result;
}

/// <summary>
/// Recursive extension method. Converts the stack to an array of its elements (bottom → top), restoring the stack.
/// Performs **only one** array allocation by creating it at the deepest (empty‑stack) frame and
/// filling indices while the recursion unwinds.
/// </summary>
public static T[] ToArray<T>(this Stack<T> stack) => BuildArray(stack, 0);


/// <summary>
/// Recursive helper for the parent ToArray.
/// <para>depth = how many elements have been popped so far (also the index to write)</para>
/// <para>When the stack is empty we allocate the array sized to <c>depth</c>.</para>
/// <para>On the way back up we restore the stack and fill <c>array[depth]</c> with <c>top</c>.</para>
/// </summary>
private static T[] BuildArray<T>(Stack<T> stack, int depth)
{
    if (stack.IsEmpty())
        return new T[depth]; // single allocation happens exactly once at the deepest call

    T top = stack.Pop();
    T[] array = BuildArray(stack, depth + 1); // recurse first, depth grows
    array[depth] = top;                       // fill while unwinding (bottom→top order)
    stack.Push(top);                          // restore
    return array;
}

public static void CompareToArrayPerformance()
{
    const int N = 8000;
    // Build a template stack
    var template = new Stack<int>();
    for (int i = 0; i < N; i++)
        template.Push(i);

    // Helper to clone the stack
    Stack<int> Clone(Stack<int> orig)
    {
        var temp = new Stack<int>();
        var clone = new Stack<int>();
        while (!orig.IsEmpty())
            temp.Push(orig.Pop());
        while (!temp.IsEmpty())
        {
            var v = temp.Pop();
            orig.Push(v);
            clone.Push(v);
        }
        return clone;
    }

    const int iterations = 10;
    long totalTime1 = 0, totalTime2 = 0;
    int[] samples1 = new int[iterations];
    int[] samples2 = new int[iterations];

    for (int it = 0; it < iterations; it++)
    {
        var s1 = Clone(template);
        var s2 = Clone(template);

        var sw = Stopwatch.StartNew();

        var arr2 = s2.ToArray2();
        sw.Stop(); totalTime2 += sw.ElapsedMilliseconds;

        sw.Restart();
        var arr1 = s1.ToArray();
        sw.Stop(); totalTime1 += sw.ElapsedMilliseconds;

        // Record a small sample to verify correctness
        samples1[it] = arr1.Length > 0 ? arr1[0] : int.MinValue;
        samples2[it] = arr2.Length > 0 ? arr2[0] : int.MinValue;
    }

    Console.WriteLine($"Avg ToArray:  {totalTime1 / (double)iterations:F2} ms");
    Console.WriteLine($"Avg ToArray2: {totalTime2 / (double)iterations:F2} ms");
    Console.WriteLine("Test iterations:");
    for (int it = 0; it < iterations; it++)
        Console.WriteLine($"  iter {it}: ToArray={samples1[it]}, ToArray2={samples2[it]}");
}