本期我們再通過幾個例子，加深遞歸的理解和熟練度。

上期有一個練習題：用遞歸逆序輸出一個包含整型數據的鏈表。

先完成這個練習題。

對于程序員來說，代碼是最好的溝通工具，什么都不說，上代碼：

public class Hello {    public static void main(String[] args) {LinkedList list=createLinkedList();//list.print(); 正序輸出list.revertPrint();//逆序輸出}   /*創建一個鏈表，用來測試*/public static LinkedList createLinkedList() {LinkedList list=new LinkedList();for(int i=11;i<=20;i++) {list.add(i);}return list;}
}package test;/*** 具有逆序輸出功能的鏈表類*/
public class LinkedList {// 內部類Node，代表鏈表的節點private class Node {Node next; // 指針域public int data;// 數據域public Node(int data) {this.data = data;this.next = null;}}// ----public Node head = null; // 鏈表頭// 向鏈表中插入數據public void add(int data) {Node nodeNew = new Node(data);if (null == head) {head = nodeNew;return;}Node pre = head;Node p = head.next;while (p != null) {pre = p;p = p.next;}pre.next = nodeNew;}// 正序輸出public void print() {Node p = head;while (p != null) {System.out.print(p.data + " ");p = p.next;}}// 逆序輸出public void revertPrint() {rP(head);}// 遞歸函數public void rP(Node node) {if (null == node)return;rP(node.next);System.out.print(node.data + " ");}
}

整數倒序輸出

如：

輸入整數1234，輸出為4321

輸入整數7890，輸出為0987

解題：

可以這么來看：

先輸出該數的個位數，

然后把此數/10后的到的商，再輸出此商的個位。

以此遞推下去，直到商為0( 也即最高位/10的商 )。

代碼：

    public static void main(String[] args) {Scanner sc=new Scanner(System.in);System.out.println("請輸入一個整數");int n=sc.nextInt();if(n==0) {System.out.println(0);return;}else if(n<0) {System.out.print('-');n=0-n;}p(n);}static void p(int n) {if(n==0)return;System.out.print(n%10);p(n/10);}

思考題：

輸出一個正整數的各位數字之和。

例如：輸入 1234，輸出10。

參考整數逆序輸出的思路。

走樓梯

問題描述

樓梯有N階，上樓可以一步上一階，也可以一次上二階。編一個程序，計算共有多少種不同的走法。

解題：

分析一下：
一階階梯：只有1種走法
二階階梯：有2種走法： 一次走2個階梯，或者2次都走一個階梯
三階階梯：
有2種走法：
先走1個階梯，則還剩3-1=2個階梯，走法數等于二階階梯的走法數量
先走2個階梯，則還剩3-2=1個階梯，走法數等于一階階梯的走法數量
根據加法原理：f3 = f(3-1)+f(3-2)
四階階梯：
有2種走法：
先走1個階梯，則還剩4-1=3個階梯，走法數等于三階階梯的走法數量
先走2個階梯，則還剩4-2=2個階梯，走法數等于二階階梯的走法數量
根據加法原理：f3 = f(4-1)+f(4-2)
以此類推，得到計算公式為：
f(n)=f(n-1)+f(n-2)
f(1)=1
f(2)=2

代碼：

    public static void main(String[] args) {Scanner sc=new Scanner(System.in);System.out.println("請輸入一個正整數,代表樓梯階數");int n=sc.nextInt();int step=stair(n);System.out.println(step);}static int stair(int n){if(n==1)return 1; //一階階梯，只有1種走法if(n==2)return 2; //二階階梯，有2種走法return stair(n-1)+stair(n-2);}