JS递归计算给定积木数可搭建金字塔最底层长度

需求说明 #

编写递归算法，输入积木总数量，返回可搭建金字塔的最底层行长度：

• 积木数量不足以搭建完整金字塔时，返回当前数量能支持的最大底层行长度
• 入参old、Internal、lr为内部递归参数，外部调用时无需传入

原有实现代码 #

const pir = (Input, old, Internal, lr) => {
    console.log({
        Input, Internal, lr
    });
    if (Internal === undefined || lr === undefined || old === undefined) {
        Internal = 1;
        lr = 1;
        old = 1;
    }
    console.log({
        Input, Internal, lr
    });
    if ( ( Input === Internal ) || ( Input < Internal && old > Internal ) ) {
        return lr;
    } else {
        return pir(Input, Internal, Internal + (lr + 1), lr + 1)
    }
};

问题分析 #

底层长度为n的完整金字塔所需总积木数为等差数列求和：1+2+...+n = n*(n+1)/2。
原有代码存在递归传参错误：递归调用时未正确更新old参数值，导致积木数不足完整金字塔时，判断分支无法触发，会出现无限递归栈溢出的问题。

修正后实现 #

用函数默认参数简化初始化逻辑，修正递归传参顺序，调整边界判断条件：

const pir = (Input, old = 0, total = 1, layer = 1) => {
    // 积木数刚好匹配当前层完整金字塔所需总数，返回当前层长度
    if (Input === total) return layer;
    // 积木数不足以搭建下一层完整金字塔，返回上一层的长度
    if (Input < total) return layer - 1;
    // 递归计算下一层参数
    return pir(Input, total, total + layer + 1, layer + 1);
};

验证结果 #

• 输入1，返回1，符合预期（1块积木刚好搭1层）
• 输入3，返回2，符合预期（3块积木刚好搭2层）
• 输入4，返回2，符合预期（4块积木不够搭3层所需的6块，最大底层长度为2）
• 输入6，返回3，符合预期
• 输入9，返回3，符合预期（9块不够搭4层所需的10块）
• 输入10，返回4，符合预期

内容的提问来源于stack exchange，提问作者SamuelFischerCode