递归题集

思路：

• 找重复
  • 找到一种划分方法
  • 找到递推公式或者等价转换
  • 都是父问题转化为求解子问题
• 找变化的量
  • 变化的量通常要作为参数
• 找出口

汉诺塔

function hanoi($n, $a, $b, $c) {
    if ($n == 1) {
        printf("%s -> %s \n", $a, $c);
    } else {
        hanoi($n-1, $a, $c, $b);
        printf("%s -> %s \n", $a, $c);
        hanoi($n-1, $b, $a, $c);
    }
}             
hanoi(4, 'a', 'b', 'c');
结果：
a -> b 
a -> c 
b -> c 
a -> b 
c -> a 
c -> b 
a -> b 
a -> c 
b -> c 
b -> a 
c -> a 
b -> c 
a -> b 
a -> c 
b -> c

求阶乘

/*O(n)
*求n的阶乘:f1(n):求n的阶乘-》f1(n-1) 求n-1的阶乘；
*找重复 n * (n-1)的阶乘，求n-1的阶乘是原问题的重复（规模更小）-》子问题；
*找变化 变化量作为参数；
*找边界
*/
function factorial($n) {
    //出口判断
    if ($n == 1) {
        return $n;
    }
    return $n * factorial($n - 1);
}
echo factorial(3);
结果：6

打印i-j

//O(j-i)
function p($i, $j) {
    if ($i > $j) {
        return;
    }
    print $i;
    p($i+1, $j);
}
p(2, 9);
结果：23456789

对arr所有元素求和

// O(n) 切蛋糕思想
function sum($arr, $begin) {
    $arrLength = count($arr)-1;
    if ($begin == $arrLength) {
        return $arr[$begin];
    }
    return $arr[$begin] + sum($arr, $begin+1);
}
echo sum(array(1,2,3,4), 0);
结果：10

反转字符串

//O(n)切蛋糕思想
function reverser($str, $end) {
   if ($end == 0) {
       return $str[$end];
   }
   return $str[$end].reverser($str, $end-1);
}
echo reverser('abcdefg', 6);

结果：gfedcba

最大公约数

//O(2logn)
function gcd($m, $n) {
    if($n == 0) {
        return $m;
    }
    return gcd($n, $m%$n);
}
echo gcd(30, 40);
结果：10