递归问题

<?php 

/*
递归的三大要素

第一要素：明确你这个函数想要干什么
第二要素：寻找递归结束条件
第三要素：找出函数的等价关系式

*/

//1. 阶乘
function test($n){
    if($n == 1){
        return 1;
    }
    return $n * test($n - 1);
}
//echo test(4);


//2. 青蛙跳，一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
function qingwatiao($n){
    //可以优化，很多值被重复计算了  f(8) = f(7) + f(6)    f(7) = f(6) + f(5)，这里f(6)被重复计算了，可以保存其阿里
    //这题也可以自底向上算，f(1) => f(2) => f(3) => f(4) => f(5)
    if($n <= 2){
        return $n;
    }
    
    return qingwatiao($n - 1) + qingwatiao($n - 2);
}
echo qingwatiao(15);


//3. 1234变成4321
function test1($str){
    if(strlen($str) <= 1){
        return $str;
    }
    
    $first = substr($str, 0 , 1);
    $left = substr($str, 1);
    return test1($left) . $first;
    
}
//echo test1('1234');