递归求数字降至1的最小步数程序逻辑排查求助

你的递归程序核心逻辑方向是对的，但存在几个潜在问题导致结果错误或性能异常：

1. 初始值设定的严谨性问题 #

你将possibility1、possibility2初始化为0，但递归返回的步数最小值从1开始（仅n=1返回0）。虽然在n≥1的合法输入下，初始值0不会被误判为有效步数，但这种设定不够严谨——如果输入n<1，会触发无限递归（不断调用escapingTime(n-1)），最终导致栈溢出。

2. 依赖的最小值函数可能存在实现错误 #

你的代码完全依赖minimumOfThree和minimumOfTwo函数，如果这两个函数没有正确返回最小值（比如误写成返回最大值），会直接导致所有计算结果错误。比如若minimumOfThree返回三个数中的最大值，程序会选择最长路径而非最短路径。

3. 纯递归无记忆化导致的性能与栈溢出问题 #

纯递归实现会重复计算大量子问题（比如计算escapingTime(10)时会计算escapingTime(9)、escapingTime(5)；计算escapingTime(9)时又会计算escapingTime(8)、escapingTime(3)，而计算escapingTime(5)时还会重复计算escapingTime(4)等）。对于较大的n（比如n>1000），递归深度会超过栈的默认限制，触发栈溢出，同时运行时间会急剧增加。

修复后的代码方案 #

方案1：带记忆化的递归版本 #

通过记忆化存储已计算的结果，避免重复计算，同时修正初始值逻辑：

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

// 通用最小值函数
int min(int a, int b) {
    return a < b ? a : b;
}

int minThree(int a, int b, int c) {
    return min(min(a, b), c);
}

// 记忆化数组，存储已计算的结果，使用前需初始化
int* memo;

int escapingTime(int n) {
    if (n == 1) {
        return 0;
    }
    // 已计算过，直接返回缓存结果
    if (memo[n] != -1) {
        return memo[n];
    }

    int res = INT_MAX;
    // 优先尝试减1的路径
    res = 1 + escapingTime(n - 1);
    // 若能被2整除，尝试除以2的路径
    if (n % 2 == 0) {
        res = min(res, 1 + escapingTime(n / 2));
    }
    // 若能被3整除，尝试除以3的路径
    if (n % 3 == 0) {
        res = min(res, 1 + escapingTime(n / 3));
    }

    // 缓存结果
    memo[n] = res;
    return res;
}

int main() {
    int n = 10;
    // 初始化记忆化数组，-1表示未计算
    memo = (int*)malloc((n + 1) * sizeof(int));
    for (int i = 0; i <= n; i++) {
        memo[i] = -1;
    }
    printf("最小步数：%d\n", escapingTime(n));
    free(memo);
    return 0;
}

方案2：动态规划迭代版本（更稳定，无栈溢出风险） #

迭代式动态规划完全避免递归栈的问题，效率更高：

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int escapingTime(int n) {
    if (n == 1) {
        return 0;
    }
    // dp[i]表示将i降到1的最小步数
    int* dp = (int*)malloc((n + 1) * sizeof(int));
    dp[1] = 0;

    for (int i = 2; i <= n; i++) {
        // 初始值为减1的步数
        dp[i] = 1 + dp[i - 1];
        // 若能被2整除，取更优路径
        if (i % 2 == 0) {
            dp[i] = min(dp[i], 1 + dp[i / 2]);
        }
        // 若能被3整除，取更优路径
        if (i % 3 == 0) {
            dp[i] = min(dp[i], 1 + dp[i / 3]);
        }
    }

    int res = dp[n];
    free(dp);
    return res;
}

int main() {
    int n = 10;
    printf("最小步数：%d\n", escapingTime(n));
    return 0;
}

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