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?

Answer 1

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.