简述java递归与非递归算法，0100求和，斐波那契数列，八皇后，汉诺塔问题

一：什么是递归算法？

递归算法就是直接或者间接的调用自己的方法，在达到一个条件的时候停止调用（递归出口），所以一定要找准好条件，让递归停止，否则就会是无限进行下去

&＃160;

二：递归程序设计的关键

1：找出调用中所需要的参数

2：返回的结果

3：递归调用结束的条件

&＃160;

三：递归程序注意

1：要有方法中自己调用自己

2：要有分支结构

3：要有结束的条件

&＃160;

四：简单叙述递归函数的优缺点

优点：

1：简洁清晰，实现容易，可读性好

2：在遍历的算法中，递归比循环更为简单

缺点：

1：效率低，使用递归函数是有空间和时间的消耗的。并且很多计算都是重复的，对性能有较大的影响

2：可能导致调用栈的溢出，每一次函数调用，在内存栈中分配空间，而每一个栈的容量是有限的，当递归的层级太多的时候，超出栈的容量，就会导致栈溢出。

3：递归函数需要系统的堆栈，空间消耗比非递归的要消耗很多，并且深度太大的话，系统可能会支撑不住

&＃160;

五：注意

a.简单的用循环，复杂的用递归（可以实现大部分相关问题）

b.有规律的问题，循环不方便时，使用递归是不错的建议。

c.循环方法比递归方法快，避免了一系列函数的调用，返回中涉及参数传递，返回值的额外开销，每递归一次，栈内存就多占用一截

d.能用循环，就尽量不要用递归.......

e.当递归中出现分支结构的时候（可以出现多个分支），注意每一个分支结构都要有结束条件。

f.只要函数调用了自己，不论间接或者直接，都算递归。

g.非递归函数效率高，但是较难编程，可读性较差

&＃160;

六：相关递归问题

1：　　斐波那契数列

for循环：

1 import java.util.Scanner;
2 public class Day1{
3 public static void main(String[] args){
4 System.out.println("请输入位数所显示的数字：");
5 Scanner sc = new Scanner(System.in);
6 int x = sc.nextInt();
7 int x1 = 1;
8 int x2 = 1;
9 int x3 = 0;
10 int add = 2;
11 System.out.printf("数列分别为：\n1\t1\t");
12 for(int i = 1;i<=x-2;i++)
13 {
14 //因为前两项是一样的，从第三项开始出现不同的数字，所以进行减二
15 //所定义了三个变量，x1代表第一个数字，x2代表第二个数字，x3代表第一个数字与第二个数字的和，所赋予他们的意义不要改变
16 x3 = x1+x2;
17 add = add + x3;
18 x1 = x2;
19 x2 = x3;
20 System.out.printf("%d\t",x3);
21 }
22 System.out.println("\n第"+x+"项数字为："+x3);
23 System.out.println("前"+x+"项和为："+add);
24 }
25 }

&＃160;

递归算法：

1 public class Day1{
2 public static int f(int n){
3 if(n==1||n==2){
4 return 1;
5 }else{
6 return f(n-1)+f(n-2);
7 }
8 }
9 public static void main(String[] args){
10 System.out.println(f(5));
11 }
12 }

想法：

递归算法对于一些问题来说是真的简单，斐波那契数列的公式：fn = f(n-1) + f(n - 2) （n >= 2），考虑前两个数字的话，就是1，由于从0开始，可以理解为

F0 = 0; F1 = 1; F1 = 1;正好是与计算机相对应

&＃160;

2:　　0-100数字进行相加

for循环：

1 public class Day1{
2 public static void main(String[] args){
3 int add = 0;
4 for(int i = 0;i <= 100;i++){
5 add = add + i;
6 }
7 System.out.println("0-100的和为："+add);
8 }
9 }

递归算法：

1 public class Day1{
2 public static int f(int n){
3 if(n>0)
4 return n+f(n-1);
5 return 0;
6 }//尽量有一个临界的点，if(n == 1)return 1;else return n+f(n-1);
7 public static void main(String[] args){
8 System.out.println("0-100的和为："+f(100));
9 }
10 }

&＃160;

3：八皇后

摘自百度百科，注释比较明细：

1 public class Day1 {
2 private int[] column; //同栏是否有皇后，1表示有
3 private int[] rup; //右上至左下是否有皇后
4 private int[] lup; //左上至右下是否有皇后
5 private int[] queen; //解答
6 private int num; //解答编号
7
8 public Day1() {
9 column = new int[8+1];
10 rup = new int[(2*8)+1];
11 lup = new int[(2*8)+1];
12 for (int i = 1; i <= 8; i++)
13 column[i] = 0;
14 for (int i = 1; i <= (2*8); i++)
15 rup[i] = lup[i] = 0; //初始定义全部无皇后
16 queen = new int[8+1];
17 }
18
19 public void backtrack(int i) {
20 if (i > 8) {
21 showAnswer();
22 } else {
23 for (int j = 1; j <= 8; j++) {
24 if ((column[j] == 0) && (rup[i+j] == 0) && (lup[i-j+8] == 0)) {
25 //若无皇后
26 queen[i] = j; //设定为占用
27 column[j] = rup[i+j] = lup[i-j+8] = 1;
28 backtrack(i+1); //循环调用
29 column[j] = rup[i+j] = lup[i-j+8] = 0;
30 }
31 }
32 }
33 }
34
35 protected void showAnswer() {
36 num++;
37 System.out.println("\n解答" + num);
38 for (int y = 1; y <= 8; y++) {
39 for (int x = 1; x <= 8; x++) {
40 if(queen[y]==x) {
41 System.out.print("Q");
42 } else {
43 System.out.print(".");
44 }
45 }
46 System.out.println();
47 }
48 }
49
50 public static void main(String[] args) {
51 Day1 queen = new Day1();
52 queen.backtrack(1);
53 }
54 }

&＃160;汉诺塔问题：

稍后继续编辑，由于零散时间写的博客，过两三天就会补齐

&＃160;

七：总结

贵在坚持吧，最近被些事情忙怀了，毫不夸张的说，感觉生活下去的勇气都是断断续续的，有朋友不断的鼓励我，天将降大任于斯人也，必须苦其心志，劳其筋骨。

说句最现实的话，努力了真的是不一定成功，真的是需要一定的机遇的，但是努力的目的是什么？就是当机遇降临到你的身上的时候，你是否能抗的住它呢？努力就会给你力量！

加油！要走出属于自己的道路来！