PHP: Can someone explain how this code works? (Fibonacci)

Question

I promise this isn't homework. I'm just a curious novice.

How does this:

function f($i){return $i<2?$i:f($i-1)+f($i-2);}

(written by someone smart)

produce the same result as this

function fibonacci($n, $arr = array(0,1)){
    $arr[] = $arr[(count($arr) - 1)] + $arr[(count($arr) - 2)];
    if (count($arr) == $n) return $arr[$n - 1];
    else return fibonacci($n, $arr);
}

(mine)

I suppose I just don't get the syntax. Is there an if statement in there?

Answer 1

The operator "?" is named ternary operator. It is used like: p1?p2:p3 it says if p1 is true, then p2, else p3.

Answer 2

There is an if statement in there. It's called a ternary operator.

condition ? if true : if false

If $i is less than 2 return $i, else return f($i-1) + f($i-2). I'm assuming the recursive function calling isn't what you're having trouble understanding, but if it is there's a ton of examples of recursive fibonacci code if you google for it.

Answer 3

The first function is shorthand. Here's what it's doing

if($i < 2) { // $i < 2 ?
  return $i;
}
else { // :
  return f($i-1)+f($i-2);
}

By if it's less than two, the function doesn't have to be recalled. If it is 2 or greater, the function is recursively called.

Answer 4

The question mark is a conditional expression:

x ? a : b

evaluates to a if x is true, or b if it is false.

Answer 5

function f($i){return $i<2?$i:f($i-1)+f($i-2);}

means

function f($i)
{
    if $(i < 2)
        return $i;
    return f($i-1) + f($i-2);
}

That's a direct expression of the Fibonacci equation.

The other function creates and uses a cache of generated results: this is a significant optimization since evaluating fib(4), for example would otherwise evaluate fib(2) like 3 or 4 times, and fib(1) quite a few more.