13. 函数：递归

13. 函数：递归

递归是指一个函数重复调用本身的一种编程技巧。有一些数据结构或过程可以递归地表达为基本情况，在这个时候函数内部使用递归可以简化编写逻辑。

• 使用递归写 factorial（阶乘）函数

输入：0
输出：1

输入：1
输出：1*factorial(1-1) = 1*factorial(0) = 1 * 1 = 1

输入：3
输出：3*factorial(3-1) = 6

const { log } = console;
function factorial(n) {
    if(n === 0) return 1;
    let res = 1;
    for(let i = 2 ; i <= n ; i ++) {
        res = res * i;
    }
    return res;
}
log(factorial(10));
// -> 3628800

• 使用递归写 fibonacci（斐波那契） 函数

const { log } = console;
function fabonacci(n) {
    if(n == 0) return 0;
    if(n == 1) return 1;
    return fabonacci(n-1)+fabonacci(n-2)
}
log(fabonacci(20));
// -> 6765

• 使用递归写 sum 函数

输入：0
输出：0

输入：1
结果：1+0

输入：3
结果：3+2+1+0

const { log } = console;
function sum(n) {
    if(n === 0) return 0;
    if(n === 1) return 1;
    return sum(n-1) + n;
}
log(sum(100));
// -> 5050

• 使用递归反转数组

const { log } = console;
function reverse(arr) {
    let res = [];
    if(arr.length === 1) return arr;
    return res.concat(arr.pop(),reverse(arr))
}
log(reverse([1, 2, 3, 4, 5]));
// -> [ 5, 4, 3, 2, 1 ]

• 使用递归验证回文字符串

const { log } = console;
const str = 'ya';
function isPalindrome(str) {
    let len = str.length
    if(str[0] === str[len -1]) {
        if(len <= 3) return true;
        else {
            return isPalindrome(str.substring(1,len));
        }
    }
    else return false;
}
log(isPalindrome(str));
// -> true