5.1.2何时使用递归1．定义是递归的有许多数学公式、数列等的定义是递归的。例如，求n!和Fibonacci（斐波那契）数列等。int Fibi(int n)I/求Fibonacci数列的第n项(if (n==1 Il n==2)return 1;elsereturn Fib1(n-1)+Fib1(n-2);6/66
1. 定义是递归的 有许多数学公式、数列等的定义是递归的。例如，求n!和Fibonacci （斐波那契）数列等。 int Fib1(int n) //求Fibonacci数列的第n项 { if (n==1 || n==2) return 1; else return Fib1(n-1)+Fib1(n-2); } 6/66
数据结构是递归的2.有些数据结构是递归的。如单链表就是一种递归数据结构。//单链表结点泛型类classLinkNode<E>Edata;LinkNode<E> next;1/下一个结点的指针1/构造方法public LinkNode()【next=null; }//重载构造方法public LinkNode(E d)data=d;雀next=null;head.next也是一个单链表head= (ai,head.next)head.不带头结点单链表7/66
2. 数据结构是递归的 有些数据结构是递归的。如单链表就是一种递归数据结构。 class LinkNode<E> //单链表结点泛型类 { E data; LinkNode<E> next; //下一个结点的指针 public LinkNode() //构造方法 { next=null; } public LinkNode(E d) //重载构造方法 { data=d; next=null; } } head=（a1,head.next） head a1 a2 . an ∧ head.next也是一个单链表 不带头结点单链表 7/66
示例求一个不带头结点单链表p中所有data成员（假设为int型）之和。p.nextpublic static int Sum(LinkNode<Integer>p){if (p==null)return ;elsereturn(p.data+Sum(p.next));8/66
示例 求一个不带头结点单链表p中所有data成员（假设为int型）之和。 public static int Sum(LinkNode<Integer> p) { if (p==null) return 0; else return(p.data+Sum(p.next)); } p a1 a2 . an ∧ p.next 8/66
3．问题的求解方法是递归的Hanoi问题设Hanoi(n，x，y，z)表示将n个盘片从x塔座借助y塔座移动到z塔座上Hanoi(n-1,X,z,y);move（n，X，z）：将第n个圆盘从x移到z;Hanoi(n, X, y, z)Hanoi(n-1,y,X,z)9/66
3. 问题的求解方法是递归的 Hanoi问题 设Hanoi(n，x，y，z)表示将n个盘片从x塔座借助y塔座移动到z塔座上: Hanoi(n，x，y，z) Hanoi(n-1，x，z，y)； move(n，x，z)：将第n个圆盘从x移到z； Hanoi(n-1，y，x，z) 9/66
public static void Hanoi(int n,char X,char Y,char z)( if (n==1)//只有一个盘片的情况System.out.printf("将第%d个盘片从%c移动到%c\n",n,X,z);else1/有两个或多个盘片的情况Hanoi(n-1,X,Z,Y);System.out.printf("将第%d个盘片从%c移动到%cIn",n,X,z);Hanoi(n-1,Y,X,z);10/66
public static void Hanoi(int n,char X,char Y,char Z) { if (n==1) //只有一个盘片的情况 System.out.printf("将第%d个盘片从%c移动到%c\n",n,X,Z); else //有两个或多个盘片的情况 { Hanoi(n-1,X,Z,Y); System.out.printf("将第%d个盘片从%c移动到%c\n",n,X,Z); Hanoi(n-1,Y,X,Z); } } 10/66