java中的数学归纳法--------递归

ゝ一纸荒年。 2022-05-13 12:48 142阅读 0赞

关于递归，有几个要点：

1.严格定义递归函数作用，参数，返回值，Side-effice(边界影响)

2.先一般，后特殊（n=1时。。。。）

3.每次调用都会缩小问题规模，每次的缩小程度为1;

下面我们着重介绍以下几种递归：

package cn.itheima;
    //这是个节点类，链表中的节点中每个节点都是有value和next指向下一个节点
    public class Node {
    	private int value;
    	private Node next;
    	public Node() {}
    	public Node(int value) {
    		super();
    		this.value = value;
    	}
    	public int getValue() {
    		return value;
    	}
    	public void setValue(int value) {
    		this.value = value;
    	}
    	public Node getNext() {
    		return next;
    	}
    	public void setNext(Node next) {
    		this.next = next;
    	}
    	@Override
    	public String toString() {
    		return "Node [value=" + value + ", next=" + next + "]";
    	}
    	
    }

//创建递归创建链表的方法
    public class CreateLinkedListDema {
    	public static void main(String[] args) {
    		System.out.println(CreateLinkedList(new ArrayList()));
    		System.out.println("---------------");
    		System.out.println(CreateLinkedList(Arrays.asList(1)));
    		System.out.println("---------------");
    		System.out.println(CreateLinkedList(Arrays.asList(1,2,3,4,5,6)));
    		System.out.println("---------------");
    	}
    	//CreateLinkedList创建链表的递归方法
    	public static Node CreateLinkedList(List<Integer> list) {
    		if(list.isEmpty()) {
    			return null;
    		}
    		//创建第一个LinkedList节点
    		Node firstNode = new Node(list.get(0));
    		//第2  个节点之后
    		Node head = CreateLinkedList(list.subList(1, list.size()));
    		firstNode.setNext(head);
    		return firstNode;
    	}
    }

//反转链表元素递归方法
    public static Node reverseLinkedList(Node headNode ){
    		if(headNode==null) {
    			return null;
    		}
    		if(headNode.getNext()==null) {
    			return headNode;
    		}
    		Node reverseNode = reverseLinkedList( headNode.getNext() );
    		headNode.getNext().setNext(headNode);//将原头结点的下一个节点的下一个节点设为头结点。
    		headNode.setNext(null);//将头结点next设为null
    		return reverseNode;
    	}

//获得从数组中的元素取n个出来的组合。
    public static void combinations(List<Integer> select,List<Integer> list,int num){
    	
    		if(num==0) {
    			for(Integer i :select){//遍历结果
    				System.out.print(i);
    				System.out.print(" ");
    			}System.out.println(" ");
    			return;
    		}
    		if(list.isEmpty() ){
    			return;
    		}
    		//取了第一个元素,取下一个元素
    		select.add(list.get(0));
    		combinations(select,list.subList(1, list.size()),num-1);
    		//不取第一个元素
    		select.remove(select.size()-1);
    		combinations(select,list.subList(1, list.size()),num);
    }

## **注意：递归过多100,000会导致java.lang.Stack OverflowError!!**栈溢出!!!!这个问题是由于每次递归调用时，都会产生一个新的栈帧区块，这时就会连续的产生新的栈帧区块，区块过大就会溢出 ##

//循环法创建链表
    	public static Node CreateLinkedList1(int n) {
    		Node prev = null;//添加好的链表
    		Node head =null;//返回结果的链表
    		for(int i=1;i<n;i++) {
    			Node node = new Node(i);
    			if(prev!=null) {
    				prev.setNext(node);
    			}else {
    				head=node;
    			}
    			prev=node;
    		}return head;
    	}

//循环反转
            public static Node reverseLinkedList1(Node head){
    		Node newNode = null;//反转的节点
    		Node currentNode =head;//下个要反转的节点
    		while(currentNode!=null) {
    			Node next = currentNode.getNext();
    			currentNode.setNext(newNode);
    			newNode=currentNode;
    			currentNode=next;
    		}
    		return newNode;
    	}

delete\_if

![70][]

public Node deleteIf(Node head,int num) {
    		
    		while(head!=null&&head.getValue()==num) {
    			head=head.getNext();
    		}
                    if(head==null) {
    			return null;
    		}
    		Node prev = head;//要操作的节点
    		while(prev.getNext()!=null){
    			if(prev.getNext().getValue()==num) {
    				prev.setNext(prev.getNext().getNext());
    			}else {
    				prev=prev.getNext();
    			}
    		}
    		return head;
    	}

[70]: /images/20220513/1ae3530aef84493885abf99052d5ce07.png