递归算法练习

当我们遇到复杂问题时，最好能通过分析理解题目找出简单的方法来解决问题。今天我们一起来做一道Scratch竞赛题——“爬台阶问题”。

小明要上二楼，从一楼到二楼共十级台阶。这次小明突然想到一个问题：“我上楼时一步可以爬一级台阶也可以跨两级台阶，那么从一楼到二楼一共有多少种走法呢？”那么聪明的你可以帮小明用编程来解决这个问题吗？

首先要分析题目：假设每次爬1级台阶需要10步，这种解法用数字化来表示为1、1、1……1。如果每次爬2级台阶则表示为2、2、2、2、2。当然我们还可以1级2级台阶交叉走……怎样才能把所有可能性找出来呢？我们用编程的思路来解决，最简单算法是多层嵌套循环，这是用最基础的枚举法。还可以想一想我们讲过的递归算法，这种方法更加高效。

这道题要从后往前思考，假设小明只差最后一步就可以上第10級台阶了，这个时候只会出现两种情况：第一种是只需要走1步（步长为1）从台阶9走到台阶10;第二种是需要走2步（步长为2）从台阶8走到台阶10。这样最后一步就是从台阶9或者台阶8开始的，如果我从台阶0-8有X种办法，从台阶0-9有Y种方法，那么从0-10级台阶有多少种解法呢？那么最后一步的走法数量就等于X+Y种。这样得出结论：台阶0-10的走法等于台阶0-9的走法加台阶0-8的走法。依据这个结论继续向前思考，台阶8的走法是台阶6+台阶7;台阶9的走法是台阶8+台阶7。这样我们把这个复杂的问题就通过从后向前分段简化了，这是一种特别有趣的解题技巧。