CODEWITHSUNDEEP
c#recursiontail-recursion
ccc31807
ccc31807

Reputation: 773

Tail recursion, how do we eliminate the return statement?

Here is a tail recursive C# program that sums the squares of 1 through 10. It works, except for the last else in AddSquares2(). It does not work because C# seems to demand a return statement in every path in a method that returns a value. However, I shouldn't need a return statement in a tail recursive method such as this one. See the comment.

Is this just an idiosyncrasy of C#? Or is there a way to tell the compiler that I know what I'm doing and that I don't want every path to return a value?

Here is my program:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Recursive
{
    class Program
    {
        static void Main(string[] args)
        {
            int start = 1;
            int end = 10;
            int sum = 0;
            AddSquares(start, end, sum);
            sum = AddSquares2(start, end, sum);
        }

        private static int AddSquares2(int start, int end, int sum)
        {
            Console.WriteLine($"AddSquares2({start}, {end}, {sum})");
            if (start > end)
                return (sum);
            else
                //should not have to return anything here
                return(AddSquares2(start + 1, end, sum + start * start));
        }

        private static void AddSquares(int start, int end, int sum)
        {
            Console.WriteLine($"AddSquares({start}, {end}, {sum})");
            if (start > end)
                Console.WriteLine($"  The total sum is {sum}");
            else
                AddSquares(start + 1, end, sum + start * start);
        }
    }
}

Here is the output:

 AddSquares(1, 10, 0)
    AddSquares(2, 10, 1)
    AddSquares(3, 10, 5)
    AddSquares(4, 10, 14)
    AddSquares(5, 10, 30)
    AddSquares(6, 10, 55)
    AddSquares(7, 10, 91)
    AddSquares(8, 10, 140)
    AddSquares(9, 10, 204)
    AddSquares(10, 10, 285)
    AddSquares(11, 10, 385)
      The total sum is 385
    AddSquares2(1, 10, 0)
    AddSquares2(2, 10, 1)
    AddSquares2(3, 10, 5)
    AddSquares2(4, 10, 14)
    AddSquares2(5, 10, 30)
    AddSquares2(6, 10, 55)
    AddSquares2(7, 10, 91)
    AddSquares2(8, 10, 140)
    AddSquares2(9, 10, 204)
    AddSquares2(10, 10, 285)
    AddSquares2(11, 10, 385)
      The total sum is 385

Upvotes: 0

Views: 603

Answers (3)

Dave M
Dave M

Reputation: 3033

The Question is correct in its assertion that it shouldn't need to "return", but it depends on your meaning of "return". In a low-level sense, if a tail call is performed, then no "ret" instruction (some sort of standard stack cleanup type instruction) needs to be performed at this point, since the tail call will make the actual execution behave equivalent to a simple loop.

However, C# is not as close to the metal as that. When we write C# we specify intent and let the compiler (and/or JITter) take care of the optimizations like tail calls, method inlining and the like. The presence of the C# return keyword does not necessarily imply or force some stack cleanup. Instead it indicates the programmer's intent.

If we allow you to leave out the "return" it makes the compiler's job of understanding your intent a lot more difficult. Was the programmer aware of the optimization that would happen and intends conceptually for the method to "return", or did he mean explicitly don't do anything with the result. C# assumes the latter.

Now, if you are concerned that the fact you can't leave out the return means that a tail call can't be performed, do not worry. The compiler and JITter take care of these sorts of optimizations automatically. They take your specified intent and implement it in the most optimized manner they can. And they almost always do a better job of deciding what and when to apply these sorts of optimizations than the programmer could.

Upvotes: 1

Caius Jard
Caius Jard

Reputation: 74595

The only way you can "get away with" not using a return is to throw an error instead. It doesn't make sense to do this in your situation.

You can also avoid using a return by not providing a code path (don't have an else clause, in this situation)

You have, however, done the right thing in that you've returned the result of recursively calling AddSquares2 in your else. If you don't do this, your code for AddSquares2 will never recurse and won't work (so you DID have to return something after all! Ahh).

Recursive methods must have a point inside themselves where they return without calling themselves (to stop recursion from going forever), and also a point where they call themselves (to keep recursion going for a while)

Probably an academic exercise but perhaps worth mentioning that recursion is a form of looping that (ab)uses the call stack into providing a looping construct. Recursive methods can (and should, imho) be done using normal loops

Upvotes: 1

TheGeneral
TheGeneral

Reputation: 81473

In short, a method in C# has to have a return on all code execution paths, you may not like it but it does. The same in Maths all functions have a result, that's what functions do.

Now on saying that, the result can be undefined, Infinity, 0, null, or in the case of C# with a return type of a non-nullable int it can be 0. Which makes perfect sense given the signature.

How about we pretend for a second we could just vanish the code execution at the point of your else. If the calling method is relying on a result (and they usually do) and even if the method ended the way you propose, then what is the caller going to think? well it needs to be able to deal with the absence of a value, or not.

If you really need to know that your else doesn't produce a value, make your signature int? (nullable ) and return null, so the caller knows what to do. if its just an absence of a number for sum then make it 0, no harm done

Upvotes: 1

Related Questions