递归
递归的概念
一个方法在执行过程中调用自身, 就称为 “递归”。
递归的必要条件：
- 将原问题划分成其子问题，注意：子问题必须要与原问题的解法相同
- 递归出口（也就是要有一定的条件让递归结束，否则会死循环）
- 在写递归之前，想一想这个题目是否可以用递归公式解决。
♥♥♥ 栈存储的顺序：
按顺序打印一个数字的每一位
（例如1234 打印出 1 2 3 4）
public class Test { public static void main(String[] args) { print(1234); } public static void print(int n){ //递归结束条件，满足条件后进入打印1，返回1 if(n<10){ System.out.println(n);//先打印再返回 return ; } //递123，递12 再递1 print(n/10); //归12打印2，归123打印3 System.out.println(n%10); } }
递归求N！的阶层
public class Test { public static void main(String[] args) { System.out.println(fac(5)); } public static int fac(int n){ //条件必不可少 if(n==1){ return 1; } int sum= n * fac(n-1); return sum; } }
递归求1+2+3+4+…+10
public class Test { public static void main(String[] args) { System.out.println(sum(10)); } public static int sum(int n){ if(n==1){ return 1; } return n+sum(n-1); } }
写一个递归方法，输入一个非负整数。返回组成它的数字之和（不熟）
例如，输入1729，返回1+7+2+9，它的和是19
public class Test { public static void main(String[] args) { System.out.println(sum(123)); } public static int sum(int i){ if (i<10){ return i; } return i%10+sum(i/10);//3+sum(12/10) 2+sum(1) } }
斐波那契数列（不熟）
//斐波那契数列
//不建议用递归写，太多重复的
//建议用for循环写
public class Test { public static void main(String[] args) { System.out.println(sum(5)); } public static int sum(int n){ int f1=1; int f2=1; int f3=2; if (n==1){ return 1; } if (n==2){ return 1; } for (int i = 3; i <= n; i++) { f3=f1+f2; f1=f2; f2=f3; } return f3; } }
递归求汉诺塔（难点）
public class Test { //移动的方法，盘子是字符char类型 public static void move(char pos1,char pos2){ System.out.print(pos1 +" => "+ pos2 +" "); } //方法括号里的参数有盘子个数，三根柱子 public static void hanio(int n,char pos1,char pos2,char pos3){ if(n==1){ move(pos1,pos3); return ; } //递归，把n-1个盘子从起始位置移动到pos3，再把pos3的盘子移到pos2 hanio(n-1,pos1,pos3,pos2); //把pos1的盘子移到pos3 move(pos1,pos3); //把pos2的盘子移到pos1上，再把pos1的盘子移到pos3上 hanio(n-1,pos2,pos1,pos3); } public static void main(String[] args) { hanio(1,'A','B','C');//第一个盘子 System.out.println(); hanio(2,'A','B','C');//第二个盘子 System.out.println(); hanio(3,'A','B','C');//第三个盘子 } }
总结
今天专攻递归，写了几道题目感觉还不错，对递归的思维更深刻了。
