Tim Van Wassenhove home

Yesterday i already wrote that an interative implementation for a recursive function is more efficient. And i gave you an example of the fibonacci function. Well, today i am here to present you an implementation for every recursive function.

class Math
{
  // calculate the linear combination  
  // fe:     
  // coefficients = array(1, 2, 3)   
  // values = array(4, 5, 6)     
  // returns: (1 \* 4) + (2 \* 5) + (3 * 6)
  function lc($coefficients, $values)     
  {        
    if (count($coefficients) != count($values))        
    {             
      return false;      
    }

    $result = 0;        
    for ($i = 0; $i < count($coefficients); ++$i)    
    {          
      $result += $coefficients[$i] * $values[$i];        
    }         
    return $result;     
  }

  // lookup the value for the recursive function     
  // fe:     
  // n: 3      
  // coefficients = array(a, b)    
  // initvalues = array(0, 1)     
  // returns: 2    
  // this is the same as f(n) = (a \* (n-2)) + (b \* (n-1))    
  function recursive($n, $coefficients, $initvalues)    
  {          
    if ($n < count($initvalues))         
    {             
      return $initvalues[$n];          
    }

    for ($i = count($initvalues); $i <= $n; ++$i)        
    {            
      $result = Math::lc($coefficients, $initvalues);            
      array_shift($initvalues);             
      array_push($initvalues, $result);        
    }
    return $result;    
  }
}

As an example we use this class to calculate fibonacci(3):

$coefficients = array(1, 1); // f(n) = (1 \* f(n-2)) + (1 \* f(n-1))
$initvalues = array(0, 1); // f(0) = 0 and f(1) = 1
echo Math::recursive(3, $coefficients, $initvalues);