Re: How to write a nonrecursive program ?

richard@xxxxxxxxxxxxxxx (Richard Tobin) wrote:

In article <20081121220433.050f52f1@xxxxxxxx>,
Ertugrul Söylemez <es@xxxxxxxx> wrote:

In most cases, you can easily get around this by just adding an
accumulation parameter:

int factorial(int x, int b) {
if (x == 0) return b;
return factorial(x - 1, b*x);
}

I'd be interested to see how you algorithmically turn the original
recursive factorial into that, as opposed to coming up with a
completely different, but tail-recursive, method.

Note that the tail-recursive version performs the multiplications in a
different order, so an algorithmic transformation needs to know about
the associativity of multiplication.

In functional terms, this is actually the difference between left folds
and right folds. The recursive version is a right fold. Correct would
be to write a left fold in the first place, because the right fold is,
as you said, a completely different algorithm.


Greets,
Ertugrul.


--
nightmare = unsafePerformIO (getWrongWife >>= sex)

.

Relevant Pages

  • THEOREM: I <= 4M in GF(p^n)
    ... That is field inversion is no more costly than the cost of 4 field ... pass algorithm that in the end computes the inverses in leafs). ... int NX= high_digit, ... Inversion" because of the number of extension field multiplications ...
    (comp.theory)
  • Re: vim: command to fold C++ comments?
    ... These comments are defined as a region tagged as a fold. ... int efgh() ... the fold over the function body; I can unfold teh function ...
    (comp.editors)
  • Re: Hint instructions
    ... cute way of trying to fold ... then takes all the scaffolding away to reveal self-optimized code. ... The furthest I've ever gone in this direction was to write 6 different inline asm versions of the same algorithm, then determine at runtime which of them turned out to be the fastest on the current cpu/data combination. ...
    (comp.arch)
  • Re: Online poker RNG...
    ... fold, etc., etc.) and part from-the-gut (based on years of playing B&M ... "Good colluders know, as part of their colluding, how ... My particular worry is that, as was shown possible in 1999 ... knew exactly what algorithm was being used. ...
    (sci.math)
  • Re: fold over list of tuples
    ... I'm fairly comfortable with the basics of fold, map, ... list: List Int ... and want to add the first element of each list. ...
    (comp.lang.functional)