台阶走法递归

AQZSG • 2025-04-29 12:49 • 编程

台阶走法递归是一个经典的递归问题，在计算机算法中有着广泛的应用。本篇文章将从递归的思想出发，详细分析如何解决这个问题。

一、递归基础知识

递归是指一个函数直接或间接地调用自身。递归函数通常有两个条件：递归终止条件和递归调用条件。在递归调用的过程中，每次都会将参数传入一个新的函数中，这些新的函数形成一个递归调用的栈。当递归终止条件满足时，逐层返回结果，直到回到最开始的函数。

递归函数可以方便地解决复杂问题，但是也容易导致时间和空间的浪费。因此，在编写递归函数时需要特别注意终止条件和递归调用条件的设计。

二、问题描述

在一排有n个台阶的楼梯上，每次可以向上迈1个或2个台阶，问到达第n个台阶有多少种走法。

三、解决方案

方法1：暴力递归

暴力递归即直接调用递归函数，计算所有可能的走法。由于存在大量重复计算，这种方法会导致时间复杂度为O(2^n)。


public static int countSteps(int n) {
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else {
        return countSteps(n - 1) + countSteps(n - 2);
    }
}

方法2：递归加缓存

递归加缓存即使用一个数组来记录每个n对应的走法数目，避免了大量重复的计算。这个方法的时间复杂度为O(n), 空间复杂度同样为O(n)。


public static int countStepsWithCache(int n) {
    int[] cache = new int[n + 1];
    return countSteps(n, cache);
}

private static int countSteps(int n, int[] cache) {
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else if (cache[n] > 0) {
        return cache[n];
    } else {
        int num = countSteps(n - 1, cache) + countSteps(n - 2, cache);
        cache[n] = num;
        return num;
    }
}

方法3：迭代法

迭代法即使用循环来计算结果。由于在计算过程中只需要用到前两个结果，因此只需要使用两个变量来保存结果。时间复杂度同样为O(n)。


public static int countStepsWithLoop(int n) {
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else {
        int a = 1, b = 2, c = 0;
        for (int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

四、总结

如上述，我们可以通过暴力递归、递归加缓存以及迭代法等方式来解决问题。在实际应用中，需要根据具体的问题来选择合适的算法。

原创文章，作者：AQZSG，如若转载，请注明出处：https://www.506064.com/n/375114.html