---
title: Java SE笔记： 递归的例子：楼梯算法
date: 2016-07-22 21:10:00
updated: 2016-07-22 21:10:00
description: "递归的例子：楼梯算法"
categories: [个人笔记]
tags: [Java, Java SE笔记]
---

n层阶梯的楼梯，每次可以走1~2层阶梯，打印列举所有走法。
            // 比如
            // 走1层的可能走法 (1种)
            // 1
            // 走2层的可能走法(2种)
            // 1 1
            // 2
            // 走3层的可能走法(3种)
            // 1 1 1
            // 1 2
            // 2 1
            // 走4层的可能走法(5种)
            // 1 1 1 1
            // 1 1 2
            // 2 2
            // 2 1 1
            // 1 2 1
            // 走n层的走法

```java
private static void step(int n, int[] a)
{
    int sum = 0;
    for (int i = 0; i < a.length; i++) 
    {
        sum += a[i];
    }
    if (sum <= n - 2) 
    {
        for (int i = 1; i <= 2; i++) 
        {
            int x = 0;
            for (int j = 0; j < a.length; j++) 
            {
                if (a[j] == 0) 
                {
                    x = j;
                    break;
                }
            }
            a[x] = i;
            step(n, a);
        }
    } 
    else if (sum == n - 1) 
    {
        int x = 0;
        for (int j = 0; j < a.length; j++) 
        {
            if (a[j] == 0) 
            {
                x = j;
                break;
            }
        }
        a[x] = 1;
        step(n, a);
    } 
    else 
    {
        for (int i = 0; i < a.length; i++) 
        {
            if (a[i] != 0) 
            {
                System.out.print(a[i] + " ");
            }
        }
        System.out.println();
    }
    int x = 0;// 每次step方法执行到最后的时候，要擦除这次往a数组中赋的值！
    for (int j = a.length - 1; j >= 0; j--) 
    {
        if (a[j] != 0) 
        {
            x = j;
            break;
        }
    }
    a[x] = 0;
    // 局部变量是数组，step方法根据数组的各位数总和判断是否再继续调用，当执行到最后，局部变量数组
    // 又变成结果输出，step方法顺利执行完，此时将执行上一层的step方法，该结果有要作为局部变量使用
    // 如果不改结果，程序逻辑将会出错！那么想到要在输出结果后把变量的上一次赋值擦除，那么程序能继续
    // 正确运行，然而当上一层的step方法执行完后，又要返回更上一层，此时没有执行到输出结果的那个分支，
    // 那么变量又会出错，所以经分析，应该在每一个step方法的结束处更改变量。测试成功！
}
```

![](/images/javase_7.jpg)