数据结构-递归（二）

爆栈问题（栈溢出）：

例子：

public static void main(String[] args) {
    System.out.println(f(15000));
}
private static long f(long n) {
    if (n == 0) return 0;
    return n + f(n - 1);
}

递归需要在所有方法结束之后才会进行释放资源，因此当调用的方法足够多的时候，就会让内存占满，从而发成栈溢出事件

因此，我们出现了尾调用和尾递归

尾调用：

函数的最后一步是调用函数，成为尾调用

1
2
3

function a() {
    return b()
}

这些方法不是：

function a() {
    const c = b()
    return c
}
function a() {
    return b() + 1
}
function a(x) {
    return b() + x
}

尾递归：最后调用的函数是他本身

如何解决尾递归？

把尾递归转化为迭代

private static long f(long n, long accumulator) {
    while (n != 1) {
        accumulator += n;
        n--;
    }
    return accumulator + 1;
}

code

#数据结构

数据结构-递归（二）

https://www.zheep.top/2024/12/01/数据结构-递归（二）/

作者

西行寺岩羊

发布于

2024年12月1日

许可协议

数据结构-递归（三）上一篇

数据结构-递归（一）下一篇