Recursive Fibonacci with Generic delegates

Question

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);
 }
}

• Jeff Vanzella: 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.
• Victor Tomaili: 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.
• svick: I always get confused by this kind of recursion. Is this supposed to be the Y combinator?

Answer 1

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.

Answer 2

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);
 }

• BenVlodgi: 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
• Victor Tomaili: Ok i see it now :)
• ChrisW: @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.
• BenVlodgi: @ChrisW The only thing I suggested was that he rename his T arguments
• Victor Tomaili: I already liked @ChrisW's answer. It's good option with yours.

Answer 3

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);
}

• Victor Tomaili: i use another method because i dont like = null;.
• BenVlodgi: @VictorTomaili I didn't like it either... but that is a bit over-kill :D
• ergohack: Func<> fibo = null; is required to provide an instantiation, prior to the definition; somewhat like a forward reference.