什么是递归
程序调用自身的编程技巧称为递归 ,说白了,递归和普通的函数调用一样
举个栗子(求n的阶乘):
public class factorial {
public static void main(String[] args) {
int t;
int result;
Scanner s = new Scanner(System.in);
t = s.nextInt();
result = fact(n); //这里我们调用fac方法
System.out.println(t);
}
public static int fact(int n) {
if(n==1)
return 1;
return n*fact(n-1); //因为 n != 1 ,所以这里有调用了fac方法
}
}
通过这个简单的例子我们知道,递归其实就是方法的调用,不用想太复杂
这个例子加入我们输入数字4,那这个程序的执行过程如下
用递归完成递推
- 把关注点放在要求解的目标上
- 找到第n次与第n-1次执行之间的关系
- 确定第1次的返回结果
例子1:切饼问题
一块月饼,切上1刀,可分成2块,切上2刀,可分成4块,切上3刀,可分成7块……,那么切n刀,最多可分成多少块?分析可知,切第n刀可分成n-1刀的块数加n,n=0时是1块,所以可写成递归如下
public class Cut {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.println("times:");
int number = s.nextInt();
int result = Cut.c(number);
System.out.printf("pieces of cookie:%d",result);
}
public static int c(int n){
if(n==0) {
return 1;
}
else
return (n+c(n-1));
}
}
例子2:斐波那契数列
斐波那契数列指的是这样一个数列:
[图片上传失败...(image-e100c8-1602244676138)]
这个数列从第3项开始,每一项都等于前两项之和。即:F(0)=0,F(1)=1,F(2)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 3,n ∈ N*)
public class Fibonacci {
public static void main(String[] args) {
Scanner s;
s = new Scanner(System.in);
int i = s.nextInt();
int result = fibonacci(i);
System.out.println(result);
}
public static int fibonacci(int n){
if(n==1)
return 0;
if(n==2)
return 1;
return (fibonacci(n-1)+fibonacci(n-2));
}
}
模拟连续发生的动作
- 搞清楚 连续发生的动作是什么
- 搞清楚 不同次动作之间的关系
- 搞清楚 边界条件是什么
例子1:十进制整数转换二进制
十进制整数转换为二进制整数采用"除2取余,逆序排列"法。具体做法是:用2整除十进制整数,可以得到一个商和余数;再用2去除商,又会得到一个商和余数,如此进行,直到商为小于1时为止,然后把先得到的余数作为二进制数的低位有效位,后得到的余数作为二进制数的高位有效位,依次排列起来。
public class convert {
public static void main(String[] args) {
int i;
Scanner s = new Scanner(System.in);
i = s.nextInt();
con(i);
}
public static void con(int i) {
if(i/2 != 0) {
con(i/2);
System.out.print(i%2);
}
else
System.out.print(i);
}
}
例子2:汉诺塔问题
相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。
汉诺塔问题图示
import java.util.*;
public class hanoi {
static int i=0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
move(n,'A','B','C');
}
public static void move(int n,char a,char b,char c) {
//用a,b,c三个变量表示三个柱子
if(n==1) {
//如果只有1个盘子,那就把盘子从a柱子移动到c柱子
i++;
System.out.printf("第%d步:",i);
System.out.println("把一个盘子从: " +a+" 移到: "+c);
}
else {
//把n-1个盘子从a柱子经过c柱子移动到b柱子
move(n-1,a,c,b);
i++;
System.out.printf("第%d步:",i);
System.out.println("把一个盘子从: "+a+" 移到: "+c);
//再把n-1个盘子从b柱子经过a柱子移动到c柱子
move(n-1,b,a,c);
}
}
}
进行“自动的分析”
先假设有一个函数能给出答案
在利用这个函数的前提下,分析如何解决问题
搞清楚最简单的情况下答案是什么
例子1:逆波兰表达式
逆波兰表达式是一种把运算符前置的算术表达式。
如2 + 3的逆波兰表达式为+ 2 3
如(2 +3)*4 的逆波兰表达式为 x + 2 3 4
编写程序求解任一包含+ - * /四个运算符的逆波兰表达式的值
输入:x + 11.0 12.0 + 24.0 35.0
输出:1357.0