C++: Anonymous Recursion

While implementing a recursive function, it often happens that we must resort to a separate “helper function” to handle the actual recursion.

This is usually the case when directly calling the current function would waste too many resources (stack space, execution time), cause unwanted side-effects, and/or the function doesn’t have the right arguments and/or return values.

So we end up inventing some silly name like “foo2” or “foo_helper”. I have always found it painful to come up with a proper name, and see a quite some disadvantages:

You have to think up a name, which then pollutes the namespace
A function is created which is called from nowhere else
The program flow in the source code is interrupted

Some languages allow you to embed recursion directly in-place. This might work via a label, a local gosub instruction, or some special keyword.

Anonymous recursion can also be accomplished using the Y combinator.

If possible, demonstrate this by writing the recursive version of the Fibonacci function (see Fibonacci sequence) which checks for a negative argument before doing the actual recursion.

In C++ (as of the 2003 version of the standard, possibly earlier), we can declare class within a function scope. By giving that class a public static member function, we can create a function whose symbol name is only known to the function in which the class was derived.

double fib(double n)
{
	if(n < 0)
	{
		throw "Invalid argument passed to fib";
	}
	else
	{
		struct actual_fib
		{
			static double calc(double n)
			{
				if(n < 2)
				{
					return n;
				}
				else
				{
					return calc(n-1) + calc(n-2);
				}
			}
		};

		return actual_fib::calc(n);
	}
}