CODEWITHSUNDEEP
functionrecursion
mehedi doha
mehedi doha

Reputation: 139

Need clear concept of Recursive function at beginning stage

today 1st time i'm trying to learn recursive function thru online tutorials but stuck at beginning stage. i found below code but its provide me 'output: 1' against any value. so, i need better explanation of that:

function factorial($n){
if($n==0){
return 1;
}
return fact($n, 1);
}
function fact($i, $j){
if($i<1){
return 1;}
else {
return fact($i-1, $i*$j);
}
}
echo factorial(5);

one more thing, i need clarification of how below return method:

return fact($i-1, $i*$j);

will work to convey single value from two parameters. any1 plsss give me some ideas regarding this issue to clear my concept. Thnx in advance..

Upvotes: 0

Views: 128

Answers (1)

Anaphory
Anaphory

Reputation: 6400

You have a function factorial here that calls a recursive function fact. A recursive function always works like this:

  • If you call it with a “trivial” argument, it can immediately give you the answer. In your code, that is the part saying if($i<1){ return $j; } (As per the comment of @Sreenath)

  • If the argument is more “complicated”, the function simplifies the argument (that is $i-1 in your example: The trivial case is $i<1, so making $i smaller makes the argument easier in some way) and then calls itself with the simpler argument and possibly some additional information, which is where the fact($i-1, $i*$j) call comes from.

So the recursive function fact here works doing the following thing:

fact(i, j) = fact(i-1, i*j)
 = fact(i-2, (i-1)*(i*j)) = fact(i-3, (i-2)*(i-1)*i*j)
 = ... = fact(1, (i-(i-1)) * (i-(i-2)) * ... * (i-1) * i * j)
 = fact(0, (i-i) * (i-(i-1)) * (i-(i-2)) * ... * (i-1) * i * j)
 = (i-i) * (i-(i-1)) * (i-(i-2)) * ... * (i-1) * i * j # Because 0<1
 = i! * j

Now if you want just the factorial, you need to call fact with 1 as second argument, just as you do in return fact($n, 1);.

function factorial($n){
  if($n==0){ # The trivial case
    return 1;
  }
  # Every other case is "complicated": call a specialized function.
  return fact($n, 1);
}

function fact($i, $j){
  # Helper function: returns i!*j, doing a recursive calculation.
  if($i<1){ # The trivial case
    return j;  # i!*j for i<1 is just j
  }
  else { # The "complicated" case:
    return fact(
        $i-1,  # Simplify the argument
        $i*$j  # Pass my current state down
      ); # And call myself with the simpler argument and the internal state.
  }
}

# Test it: This should return 5!=120
echo factorial(5);

Upvotes: 1

Related Questions