递归的总结和案例

①使用递归的方法获取1-100的总和

function sum(num){
    if(num === 1){
        return num = 1
    }else {
        return num+sum(num-1)
    }
}
let num = 100

let numSum = sum(num)

console.log(numSum,'numSum')

②数组求和

function arrSum (arr){
    let len = arr.length
    if(len== 0){
        return 0
    }else if(len == 1){
        return arr[0]
    }else {
        return arr[0] + arrSum(arr.slice(1))
    }
}
let arr = [1,2,3,4,5]
let lastSum = arrSum(arr)
console.log(lastSum,'lastSum')

执行顺序

• 1+sum(2,3,4,5)
• 1+2+sum(3,4,5)
• 1+2+3(4,5)
• 1+2+3+4+sum(5)
• 1+2+3+4+5
• 1+2+3+9
• 1+2+12
• 1+14
• 15

③数组转树

        let data = [{
                id: "01",
                pid: "",
                "name": "老王"
            },
            {
                id: "02",
                pid: "01",
                "name": "小张"
            }
        ]

  function fn(data, rootId = '') {
            const children = []      //定义一个空数组
            data.forEach(item => {
                if (item.pid === rootId) {    //如果每一项的pid=rootId就添加到数组里
                    children.push(item)
                    item.children = fn(data, item.id)
                }
            });
            return children
        }

执行顺序:

④斐波纳契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列

        function Fibonacci(n) {
            return  n <= 1?1:Fibonacci(n - 1) + Fibonacci(n - 2)
        }

递归的总结:

问:

为什么递归不需要用新的字段存储每次的结果呢?

sum(5) = 5 + sum(4)
= 5 + (4 + sum(3))
= 5 + (4 + (3 + sum(2)))
= 5 + (4 + (3 + (2 + sum(1))))
= 5 + (4 + (3 + (2 + 1)))
= 5 + (4 + (3 + 3))
= 5 + (4 + 6)
= 5 + 10
= 15
为什么不设置一个新字段来存储每次递归的值,然后最后在想加得出最后的结果?

为什么递归是这样的形式,假设n=1的时候不是直接返回1吗?为什么不定义一个字段存储sum循环过程中的每个值?

重点回答:

递归函数的特性使其不需要显式地定义一个新的字段来存储每次递归的结果。

在递归过程中，每次递归调用都会在堆栈中创建一个新的函数执行上下文，并保存该次递归的局部变量和参数。当递归终止条件满足时，递归函数会开始回溯，将每次递归的返回值传递给上一层调用，直到达到最初调用的起始点。

因此，在递归过程中，通过函数的堆栈和返回值来自动保存和传递每次递归的结果。每次递归的返回值会被用于进行后续递归调用的操作，直到达到终止条件并返回最终的累加和。

递归的优势在于它能够以一种简洁的方式表达问题的解决方法，而不需要额外的变量或数据结构来存储中间结果。这种方式通常更易于理解和实现，并且能够更直观地反映问题的本质。然而，递归也可能导致堆栈溢出或者性能下降，特别是在处理大量数据或者嵌套层级较深的情况下，需要谨慎使用并进行优化