rekurencja na iterację Opcje

[MitS]

Witam serdecznie,


mam taki oto problem.
chciałbym zamienić taki kod:

[PHP] pobierz, plaintext 
<?php
function funA($x){
    if(0 == $x)
        return 0;
    
    return $x * funB(1 ^ ($x >> 1));
}
 
function funB($y){
    if(0 == $y)
        return 1;
    
    return $y + funA($y - 1);
}
 
echo funA(5);
?>
[PHP] pobierz, plaintext 

na postać iteracyjną ale nie wiem jak się za to zabrać, gdyż jak piszę jakieś pętle to zawsze sprowadza mi się kod do rekurencji :/
Prosił bym o pomoc.

Ten post edytował MitS 15.07.2009, 21:50:38

[grn]

Często przy usuwaniu rekurencji trzeba implementować własny stos. W tym przypadku możemy napisać:

[PHP] pobierz, plaintext 
<?php
function fn($x)
{
  $stack = array();
 
  while(true)
  {
    array_push($stack, $x);
    if($x == 0)
    {
      break;
    }
 
    $y = (1 ^ ($x >> 1));
    array_push($stack, $y);
    if($y == 0)
    {
      break;
    }
 
    $x = $y - 1;
  }
 
  $ret = (count($stack) % 2 ? 0 : 1);
  if($ret == 0)
  {
    array_pop($stack);
  }
 
  while(!empty($stack))
  {
    $ret += array_pop($stack);
    $ret *= array_pop($stack);
  }
 
  return $ret;
}
?>
[PHP] pobierz, plaintext 

Pierwsza pętla odkłada argumenty przekazywane do funkcji funA i funB. Gdy po jej wykonaniu na stosie znajduje się nieparzysta ilość elementów, to ostatnim wywołaniem rekurencyjnym było wywołanie funkcji funA. Wtedy wykonujemy pojedyncze działanie. Na stosie pozostaje parzysta ilość elementów. Druga pętla oblicza wartości zwracane przez poszczególne wywołania.

[MitS]

dzięki bardzo, w ogóle nie brałem pod uwagę stosu dlatego nie wychodziło
Pozdrawiam

[Zyx]

Jeśli masz PHP 5.3, to użyj struktur danych dostępnych w SPL-u. O rekurencji swego czasu pisałem u siebie na blogu (niestety, SPL nie miał jeszcze wtedy struktur danych):

http://www.zyxist.com/pokaz.php/pozbadz_sie_rekurencji