php recursion error factoring
题
so I am new at the idea of recursion and i wrote this simple code to factor a number ($n) this is the code:
$n = 120;
$y = 1;
function factor($n, $y) {
if($y > $n) {
return 1;
} else {
$x = $n / $y;
list($whole, $dec) = array_pad(explode('.', $x), 2, Null);
if($dec == '') {
echo 'x:' . $x . ' y:' . $y . '</br>';
return factor($n, ($y + 1));
}
}
}
this is what the code outputs:
x:120 y:1
x:60 y:2
x:40 y:3
x:30 y:4
x:24 y:5
x:20 y:6
so my question is why does this stop before it completes?
解决方案
Your next step would be 120 / 7 which equals 17.142857....
So this check fails and as such the recursion does not happen:
if($dec=='') // $dec would equal to 142857.....
{
echo'x:'.$x.' y:'.$y.'</br>';
return factor($n,($y+1));
}
其他提示
else
{
$x=$n/$y;
list($whole,$dec)=array_pad(explode('.', number_format($x)), 2, Null);
if($dec=='')
{
echo'x:'.$x.' y:'.$y.'</br>';
return factor($n,($y+1));
}
}
PART OF DECIMAL LIMITATION
There are two things I see wrong with your example:
- Your recursion stops the first time it encounters a fractional value. The tail recursion (
return factor($n, $y + 1);
) only occurs when$dec == ''
. Otherwise, the function simply exits. That's why it stops when$y
is 7. - Your condition for ending recursion (
$y > $n
) is incorrect. You want to break the recursion when the divisor is greater than the quotient — i.e., when$y > $x
— because that means you've found all the integer factors.
I think this is what you want:
$n = 120;
$y = 1;
function factor($n, $y) {
$x = $n / $y;
if($y > $x) {
return 1;
} else {
list($whole, $dec) = array_pad(explode('.', $x), 2, Null);
if($dec == '') {
echo 'x:' . $x . ' y:' . $y . "</br>\n";
}
return factor($n, ($y + 1));
}
}
echo factor($n, $y);
不隶属于 StackOverflow