递归

• 特点：
  1.函数调用函数自身 基于栈
  2.但是不能无限调用 必须有一个结束点 终点
  3.递归不能够解决深度过大(n)的问题
  4.到底用不用递归？ 但凡是迭代的问题都可以用递归 但是不代表递归的问题可以用迭代解决！
  5.用迭代是人，用递归是神！

• 分治算法，是一种思想
  分而治之，就是将一个更大的问题进行拆分 拆分出若干个更小的问题 直到该问题不可再拆分为止

求和

package recursion;

public class AddRecursion {
	public static int add(int num){
		if(num==1){
			return 1;
		}
		//等于它前面的总和加它本身
		return add(num-1)+num;
	}
}

菲波那切数列

package recursion;

public class Fibo {
	public static long fibo(int n){
		if(n<=0){
			throw new IllegalArgumentException("非法参数");
		}
		if(n==1||n==2){
			return 1;
		}
		//返回前两项都的和
		return fibo(n-2)+fibo(n-1);
	}
}

八皇后问题

红框代表皇后，一共有92种排法

java代码实现如下

package leetcode;

public class EightQueen {
	static int count = 0;// 记录第几种

	public static void main(String[] args) {
		int[][] cotent = new int[8][8];
		eightQueen(0, cotent);
	}

	public static boolean noDanger(int row, int col, int[][] arr) {
		//只需判断上、左上、右上方
		// 上
		for (int r = row-1; r >= 0; r--) {
			if (arr[r][col] == 1) {
				return false;
			}
		}
		// 左上
		for (int r = row-1, c = col-1; r >= 0 && c >= 0; r--, c--) {
			if (arr[r][c] == 1) {
				return false;
			}
		}
		// 右上
		for (int r = row-1, c = col+1; r >= 0 && c < arr[0].length; r--, c++) {
			if (arr[r][c] == 1) {
				return false;
			}
		}
		return true;
	}

	public static void eightQueen(int row, int[][] arr) {
		if (row == 8) {
			//当8行都有皇后的时候说明满足条件
			System.out.println("第" + (++count) + "种");
			for (int i = 0; i < arr.length; i++) {
				for (int j = 0; j < arr[i].length; j++) {
					System.out.print(arr[i][j] + " ");
				}
				System.out.println();
			}
		} else {
			int[][] newArr = new int[8][8];
			for (int i = 0; i < arr.length; i++) {
				for (int j = 0; j < arr[i].length; j++) {
					newArr[i][j] = arr[i][j];
				}
			}
			//每一行从左到右检查
			for (int col = 0; col < 8; col++) {
				
				if (noDanger(row, col, newArr)) {
					for (int c = 0; c < 8; c++) {
						newArr[row][c] = 0;
					}
					newArr[row][col] = 1;
					//上一行有皇后就进入下一行检查
					eightQueen(row + 1, newArr);
				}
			}
		}

	}
}

汉诺塔问题

import java.util.ArrayList;
import java.util.List;
public class Hano {
	static List<Integer> p1=new ArrayList<>();
	static List<Integer> p2=new ArrayList<>();
	static List<Integer> p3=new ArrayList<>();
	public static void execute(List<Integer> from,List<Integer> mid, List<Integer> to,int level){
		if(level==1){
			to.add(0,from.remove(0));
		}else{
			//将除了最后一个，先移动到辅助盘
			execute(from,to,mid,level-1);
			//将最后一个移动到目标盘
			to.add(0,from.remove(0));
			//再将辅助盘的移动到目标盘
			execute(mid,from,to,level-1);
		}	
	}
}

递归实现链表

package recursion;
/**
 * 递归实现链表
 * @author zhang
 *
 */
public class LinkedListRecursion {
	public static void main(String[] args) {
		LinkedListRecursion link=new LinkedListRecursion();
		link.add(1);
		link.add(2);
		link.add(3);
		System.out.println(link.toString());
		link.remove();
		link.remove();
		System.out.println(link.toString());
	}
	private Node head;
	private static class Node{
		int date;
		Node next;
	}
	public LinkedListRecursion(){
		head=new Node();
		head.date=0;
		head.next=null;
	}
	//删除链表最后一个元素
	public void remove(){
		remove(head);
	}
	private Node remove(Node head) {
		if(head.next==null){
			//最后一个节点返回为空
			return null;
		}else{
			//倒数第二个的吓一跳为空
			head.next=remove(head.next);
			return head;
		}
		
	}
	//递归尾插法
	public void add(int e){
		add(head,e);
	}
	private void add(Node head, int e) {
		if(head.next==null){
			Node n=new Node();
			n.date=e;
			n.next=head.next;
			head.next=n;
		}else{
			add(head.next,e);
		}
	}
	@Override
	public String toString() {
		StringBuilder sb=new StringBuilder();
		sb.append("[");
		toString(head, sb);
		return sb.toString();
	}
	private void toString(Node head,StringBuilder sb){
		if(head.next==null){
			sb.append(head.date+"]");
		}else{
			sb.append(head.date+",");
			toString(head.next,sb);
		}
	}
}