Logic of implementing Recursion and Tail Recursion

Question

I have written the code to sum up elements of an array with

Recursion

 static int sum(int[] array)
        {

            if (array.Length == 1)
                return array[0];

            else
            {
                int[] newArr = new int[array.Length - 1];
                for (int i = 1; i < array.Length; i++)
                {
                    newArr[i - 1] = array[i];
                }

                return array[0] + sum(newArr);
            }
        }

and with

Tail Recursion

 static int sumTR(int[] array, int sum)
        {
            //base case
            if (array.Length == 1)
                return array[0] + sum;
            else
            {
                  //tail recursive case
                int[] newArr = new int[array.Length - 1];

                for (int i = 1; i < array.Length; i++)
                    newArr[i - 1] = array[i];

               
                return sumTR(newArr, array[0] + sum);
            }
        }

As I understood, in the tail recursion the base method shouldn't be waiting for the recursive method to finish executing and shouldn't be dependent on its output. Is this implementation the right way to achieve that?

Well, the recursive call will still need to be completed, at least conceptually, before the return, but with your second way here the recursive call and return can conceptually be transformed by the compiler into setting the input parameters and doing a `goto method entry point`, which should make it considerably faster. — 500 - Internal Server Error, Jun 15 '21 at 14:58

JonasH · Answer 1 · 2021-06-16T08:07:25.517

As I understood, in the tail recursion the base method shouldn't be waiting for the recursive method to finish executing and shouldn't be dependent on its output

That is not quite correct. Tail recursion mostly enables the compiler to apply tail call optimization (if supported), i.e. to rewrite the recursion to a regular loop instead. This has the advantage reduced memory usage in the stack. It has nothing to do with 'not waiting'.

In the first example it has to keep one stack frame for each item in the list, and if you have a long list there is a chance you will run out of stack memory and get a stackoverflow.

In the tail recursive case the current stack frame is no longer needed when it reaches the tail-call, so the same stack frame can be re-used for each call, and that should result in code sort of equivalent to a regular loop.

Is this implementation the right way to achieve that?

It looks fine to me. But that does not necessarily mean that the optimization will be applied, it seem to depend on the compiler version, and may have other requirements. See Why doesn't .NET/C# optimize for tail-call recursion? In general I would recommend relying on the language specification and not compiler optimization for correct function of your program.

Note that recursion is often not the ideal approach in c#. For something simple as a sum it is easier, faster, and more readable to use a regular loop. For more complicated cases, like iterating over trees, recursion can be appropriate, but then tail-call optimization will not help very much in that case.

Daniel Dearlove · Answer 2 · 2021-06-16T08:59:23.730

You can prevent making copies of the arrays by using Span. You can then slice as you recurse to the end of the array.

int sum(Span<int> span, int subtotal)
{
    return span.Length > 0
        ? sum(span.Slice(1), subtotal + span[0])
        : subtotal;
}

Span was added a while ago, in .NET Core I believe, and it has brought quite a lot of performance improvements. It has allowed more code to be moved from the C++ core to C#. Here is one article I read about the topic.

score 0 · Accepted Answer · answered Jun 15 '21 at 17:27

Recursion is a function calling itself. Tail recursion is a function calling itself in such a way that the call to itself is the last operation it performs. This is significant because a compiler that supports tail recursion can either eliminate the stack frame before the recursive call, or even transform it into a loop. In either case the accumulation of stack frames due to the repeated calls is prevented, which eliminates the possibility of overflowing the stack.

That said, your recursive sum() function works but is far from efficient: it creates new arrays for every step. There is a far easier way to calculate the sum recursively:

static int sum(int[] array)
{
    return sum(array, array.Length - 1);
}

static int sum(int[] array, int index)
{
    return array[index] + (index == 0 ? 0 :
        sum(array, index - 1));
}

The first sum() function calls the helper function with appropriate parameters, and the helper function only needs to adjust the index provided. This is done here using a ternary expression for brevity: it keeps the function as essentially a one-liner, and it illustrates clearly that the recursive call is not the last operation before returning (the addition is).

To transform this calculation into a tail-recursive one, we need to add a parameter for the intermediate result:

static int sum(int[] array)
{
    return sum(array, array.Length - 1, 0);
}

static int sum(int[] array, int index, int res)
{
    return index < 0 ? res :
        sum(array, index - 1, res + array[index]);
}

Here the addition was moved to occur before the recursive call, and the call is clearly the last operation, making the function tail-recursive.

Logic of implementing Recursion and Tail Recursion

3 Answers3