Tail recursion in loop while

2024-04-15 computer english blog

Interesting optimization of recursion using tail function. Consider this:

void RecursiveFunction(ref HashSet<Type> finalList, Type itemToAdd, ref HashSet<Type> itemsToNotAdd)
{
    // some checks and returns

    if (left)
    {
        RecursiveFunction(ref finalList, left, ref itemsToNotAdd);
    }
    else
    {
        finalList.Add(left);
    }

    if (right)
    {
        RecursiveFunction(ref finalList, right, ref itemsToNotAdd);
    }
    else
    {
        finalList.Add(right);
    }
}

And then this version:

void RecursiveFunction(ref HashSet<Type> finalList, Type itemToAdd, ref HashSet<Type> itemsToNotAdd)
{
    while (true)
    {
        // some checks and returns

        if (left)
        {
          RecursiveFunction(ref finalList, left, ref itemsToNotAdd);
        }
        else
        {
          finalList.Add(left);
        }

        if (right)
        {
            itemToAdd = right;
            continue;
        }
        finalList.Add(right);

        break;
    }
}
[comment] [Alocação sem construção]