# Recursive Fibonacci with Generic delegates

Here is a fast recursive Fibonacci-like for loop. How can it be more readable, and is it possible remove TArgs?

public static class Fibonacci
{
public static BigInteger Calculate(BigInteger number)
{
var fibo = AnonRecursiveFiboFunc<BigInteger>(
func => (step, fibo1, fibo2) => step == number
? fibo2
: func(++step, fibo1 + fibo2, fibo1));
return fibo(0, 1, 0);
}

delegate Func<TArg1, TArg2, TArg3, TArg4>
Recursive<TArg1, TArg2, TArg3, TArg4>(
Recursive<TArg1, TArg2, TArg3, TArg4> r);

private static Func<TArg, TArg, TArg, TArg>
AnonRecursiveFiboFunc<TArg>(Func<Func<TArg, TArg, TArg, TArg>,
Func<TArg, TArg, TArg, TArg>> function)
{
Recursive<TArg, TArg, TArg, TArg> recursive =
rec => (step, fibo1, fibo2) =>
function(rec(rec))(step, fibo1, fibo2);
return recursive(recursive);
}
}

• I'm not sure I understand why you are using a delegate instead of using an actual function. It seems to me like this is taking the scenic route instead of the interstate. Mar 17, 2014 at 19:41
• i use delegate because i want try it with delegates :) but i dont like multiple TArg's. And i know this is not the best way. I test what can i do with delegates. Mar 17, 2014 at 20:03
• I always get confused by this kind of recursion. Is this supposed to be the Y combinator? Mar 17, 2014 at 22:40

1. I like to say T1 T2 instead of TArg1, it just makes it more clear to me what is going on. Your code would look more like this.

delegate Func<T1, T2, T3, T4> Recursive<T1, T2, T3, T4>( Recursive<T1, T2, T3, T4> r);

private static Func<T, T, T, T> AnonRecursiveFiboFunc<T>(Func<Func<T, T, T, T>, Func<T, T, T, T>> function)
{
Recursive<T, T, T, T> recursive = rec => (step, fibo1, fibo2) => function(rec(rec))(step, fibo1, fibo2);
return recursive(recursive);
}


Other than that... this code seems pretty solid, except for the crazy lack of immediate readability :D and like mentioned in the comments the fact that you are using delegates at all here.

The opposite of BenVlodgi's answer: i.e. AnonRecursiveFiboFunc<TArg> has only one template parameter, therefore all the template arguments passed to Recursive<TArg, TArg, TArg, TArg> recursive are the same, therefore there only needs to be one of them.

You can rewrite the code as:

    delegate Func<T, T, T, T> Recursive<T>(Recursive<T> r);

private static Func<TArg, TArg, TArg, TArg>
AnonRecursiveFiboFunc<TArg>(Func<Func<TArg, TArg, TArg, TArg>,
Func<TArg, TArg, TArg, TArg>> function)
{
Recursive<TArg> recursive =
rec => (step, fibo1, fibo2) =>
function(rec(rec))(step, fibo1, fibo2);
return recursive(recursive);
}


Given that all the arguments passed to Func are the same, you can reduce it further by defining your own delegate (which I named Function3) as follows:

    delegate T Function3<T>(T arg1, T arg2, T arg3);

delegate Function3<T> Recursive<T>(Recursive<T> r);

private static Function3<TArg>
AnonRecursiveFiboFunc<TArg>(Func<Function3<TArg>,
Function3<TArg>> function)
{
Recursive<TArg> recursive =
rec => (step, fibo1, fibo2) =>
function(rec(rec))(step, fibo1, fibo2);
return recursive(recursive);
}

• I almost suggested this, but because he was using BigInteger for one type and not for the others, I didn't. Although I guess 3 of them could have indeed been collapsed.... unless I read it wrong o_O Mar 18, 2014 at 2:59
• Ok i see it now :) Mar 18, 2014 at 7:31
• @BenVlodgi He wasn't using BigInteger for one type and not for the others: BigInteger is the only type because there is only one type, i.e. the type that's passed to the AnonRecursiveFiboFunc<TArg> method, which only has one template parameter. I downvoted your answer because your suggestion made that even less clear, not "more clear" as you said. Mar 18, 2014 at 11:34
• @ChrisW The only thing I suggested was that he rename his T arguments Mar 18, 2014 at 11:43
• I already liked @ChrisW's answer. It's good option with yours. Mar 18, 2014 at 12:03

I know you said you liked using delegates, and you wanted to see what you could do with them. But I think its good to recognize when you don't need to make your own.

Here is a simpler refactored version of your code. It does not use your A non recursive function delegate. Also, technically what you were doing before was recursion still.

public static BigInteger Calculate(BigInteger number)
{
Func<BigInteger, BigInteger, BigInteger, BigInteger> fibo = null;
fibo = ((step, fibo1, fibo2) => (step == number) ? fibo2 : fibo(++step, fibo1 + fibo2, fibo1));
return fibo(0, 1, 0);
}

• i use another method because i dont like = null;. Mar 19, 2014 at 9:38
• @VictorTomaili I didn't like it either... but that is a bit over-kill :D Mar 19, 2014 at 11:58
• Func<> fibo = null; is required to provide an instantiation, prior to the definition; somewhat like a forward reference. Sep 19, 2019 at 23:16