遞歸原來可以so easy|-連載（3）

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

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

先完成這個練習題。

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

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); }