Recursive function does not return any value

Question

I want to understand why this function doesn't return anything.

function fact($n, $p = 1) {
    if ($n > 1) {
        $p *= $n--;
        fact($n, $p);
    } else {
        return $p;
    }
}

var_dump(fact(5)); // NULL

Answer 1

Because if the if condition is true then no return statement is ever encountered. Perhaps you meant this:

if ($n > 1) {
    $p *= $n--;
    return fact($n, $p); // return the value
}

Answer 2

You try to assign a variable which you did not pass by reference. Either pass $p by reference (&$p) or use a return value. In this case a return value is way better.

Secondly, $n-- is post decrement, meaning your code does not read that nicely.

function fact($n) {
    if ($n == 0) return 1;
    return $n * fact($n - 1);
}

var_dump(fact(5))

Answer 3

Recursion is a looping construct which comes from functional languages. So yes, as others noted, your function doesn't work correctly because the true branch of your if statement doesn't return anything. However, I have additional remarks about your code

function fact($n, $p = 1) {
    if ($n > 1) {
        // this makes it hard to reason about your code
        $p *= $n--;
        return fact($n, $p);
    } else {
        return $p;
    }
}

You're actually mutating two variables here in one expression. It's clever if you're trying to keep the code looking shorter, but there's actually an even better way.

function fact($n, $p = 1) {
    if ($n > 1) {
        $p *= $n--;
        // just compute the next values; no need to update $p or $n
        return fact($n - 1, $p * $n);
    } else {
        return $p;
    }
}

Now we don't have to think about how $p and $n change individually. We just know that we call fact again with the next values for each state of $p and $n.

Keep in mind, these principles are so strong in some functional programming languages that reassignment of variables likes $p and $n is not even allowed.

---

Lastly, we have to talk about your your API leak, $p. If someone were to specify a value when calling fact, they could get the wrong answer or trigger an error

// bad !
fact(5, 10); // => 1200

This is only possible because $p is actually exposed in the public API. To get around this, you have a couple of options

One of them is to do as @RonaldSwets proposes:

function fact($n) {
    // 1 is the base case, like you had for $p in your code
    if ($n == 0)
      return 1;
    // otherwise return $n times the next value
    else
      return $n * fact($n - 1);
}

Another is to use an auxiliary function which is meant only for private use

// function used by `fact`
function fact_aux ($n, $p) { 
  if ($n == 0)
    return $p;
  else
    return fact_aux($n - 1, $p * $n);
}

// function meant to be used by others
function fact ($n) {
  return fact_aux($n, 1);
}

Answer 4

you fact only return value when $n == 1. When $n > 1, you have to return value fact(n-1) in fact(n).