本期我们再通过几个例子，加深递归的理解和熟练度。

上期有一个练习题：用递归逆序输出一个包含整型数据的链表。

先完成这个练习题。

对于程序员来说，代码是最好的沟通工具，什么都不说，上代码：

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

源码、更多资深讲师相关课程资料、学习笔记请入群后向管理员免费获取，更有专业知识答疑解惑。入群即送价值499元在线课程一份。

QQ群号：560819979

敲门砖（验证信息）：高山流水