11
\$\begingroup\$

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);
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$ Mar 17, 2014 at 19:41
  • \$\begingroup\$ 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. \$\endgroup\$ Mar 17, 2014 at 20:03
  • 1
    \$\begingroup\$ I always get confused by this kind of recursion. Is this supposed to be the Y combinator? \$\endgroup\$
    – svick
    Mar 17, 2014 at 22:40

3 Answers 3

5
\$\begingroup\$
  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.

\$\endgroup\$
0
5
\$\begingroup\$

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);
    }
\$\endgroup\$
5
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – BenVlodgi
    Mar 18, 2014 at 2:59
  • \$\begingroup\$ Ok i see it now :) \$\endgroup\$ Mar 18, 2014 at 7:31
  • \$\begingroup\$ @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. \$\endgroup\$
    – ChrisW
    Mar 18, 2014 at 11:34
  • \$\begingroup\$ @ChrisW The only thing I suggested was that he rename his T arguments \$\endgroup\$
    – BenVlodgi
    Mar 18, 2014 at 11:43
  • 1
    \$\begingroup\$ I already liked @ChrisW's answer. It's good option with yours. \$\endgroup\$ Mar 18, 2014 at 12:03
3
\$\begingroup\$

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);
}
\$\endgroup\$
3
  • \$\begingroup\$ i use another method because i dont like = null;. \$\endgroup\$ Mar 19, 2014 at 9:38
  • \$\begingroup\$ @VictorTomaili I didn't like it either... but that is a bit over-kill :D \$\endgroup\$
    – BenVlodgi
    Mar 19, 2014 at 11:58
  • \$\begingroup\$ Func<> fibo = null; is required to provide an instantiation, prior to the definition; somewhat like a forward reference. \$\endgroup\$
    – ergohack
    Sep 19, 2019 at 23:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.