把递归拆出来理解(Break down recursion to understand)

这两天写几个递归算法题有点心得,记录一下

先说结论

递归过程:(判断条件)-进入–操作-(判断条件)-退出

rec(a){
if(满足退出)-退出
操作
rec(a)
(操作)
}

从链表逆序开始

// 获取节点所在位置,逆序
public int length(ListNode node, int n) {
    if (node == null)
        return 0;
    int pos = length(node.next, n) + 1;
    //获取要删除链表的前一个结点,就可以完成链表的删除
    if (pos == n + 1)
        node.next = node.next.next;
    return pos;
}

拆开

// 获取节点所在位置,逆序
public int length(ListNode node, int n) {
    if (node == null)
        return 0;
    int pos = length(ListNode node, int n) {
                    if (node == null)//exit
                        return 0;/////exit
                    int pos = length(ListNode node, int n) {
                        if (node == null)//exit
                        	 return 0;/////exit
                        int pos = length(node.next, n){...} + 1;
                       
                    }+ 1;
                    	.
                        .
                        .
                  }+1
    
    
    
    //获取要删除链表的前一个结点,就可以完成链表的删除
    if (pos == n + 1)
        node.next = node.next.next;
    return pos;
}

达到出口条件

// 获取节点所在位置,逆序
public int length(ListNode node, int n) {
    if (node == null)
        return 0;
    int pos = length(ListNode node, int n) {
                    if (node == null)//exit
                        return 0;/////exit
                    int pos = length(ListNode node, int n) {
                        if (node == null)//exit
                        	 return 0;/////exit
                        int pos = length(node.next, n){...//pos=pos+1	|6
                            if (node == null)//exit
                        		return 0;/////exit
                   			int pos = length(ListNode node, int n) {//	|3.2
                        	if (node == null)//true   					|1
                        		 return 0;/////exit 0 					|2
                                                      } + 1; //pos =0+1 |3.1
                                if (pos == n + 1)//		false			|4
    							    node.next = node.next.next;
    							return pos;				//return 0		|5
                       
                    }+ 1;
                    	.
                        .
                        .
                  }+1
    
    
    
    //获取要删除链表的前一个结点,就可以完成链表的删除
    if (pos == n + 1)
        node.next = node.next.next;
    return pos;
}

判断回文链表

ListNode temp;

public boolean isPalindrome(ListNode head) {
    temp = head;
    return check(head);
}

private boolean check(ListNode head) {
    if (head == null)
        return true;
    boolean res = check(head.next) && (temp.val == head.val);
    temp = temp.next;
    return res;
}

拆开

ListNode temp;

public boolean isPalindrome(ListNode head) {
    temp = head;
    return check(head);
}

private boolean check(ListNode head) {
    if (head == null)
        return true;
    boolean res = check(head.next){
        if (head == null)
            return true;
        boolean res = check(head.next){
            if (head == null)
                return true;
            boolean res = /*check(head.next)*/true && (temp.val == head.val);//reach exit 1
            temp = temp.next;												//下一个 		2
            return res;														//返回上级	   3
        } && (temp.val == head.val);										//判断		4
        temp = temp.next;
        return res;
    } && (temp.val == head.val);
    temp = temp.next;
    return res;
}

虽然这个题递归会重复计算一次,但是这个递归属于看得懂很难想出来

————————

These two days to write a few recursive algorithm problems, a little experience, record it

Let’s start with the conclusion

Recursive process: (judgment condition) – enter – operate – (judgment condition) – exit

rec(a){
if(满足退出)-退出
操作
rec(a)
(操作)
}

Start from the reverse order of the linked list

// 获取节点所在位置,逆序
public int length(ListNode node, int n) {
    if (node == null)
        return 0;
    int pos = length(node.next, n) + 1;
    //获取要删除链表的前一个结点,就可以完成链表的删除
    if (pos == n + 1)
        node.next = node.next.next;
    return pos;
}

open

// 获取节点所在位置,逆序
public int length(ListNode node, int n) {
    if (node == null)
        return 0;
    int pos = length(ListNode node, int n) {
                    if (node == null)//exit
                        return 0;/////exit
                    int pos = length(ListNode node, int n) {
                        if (node == null)//exit
                        	 return 0;/////exit
                        int pos = length(node.next, n){...} + 1;
                       
                    }+ 1;
                    	.
                        .
                        .
                  }+1
    
    
    
    //获取要删除链表的前一个结点,就可以完成链表的删除
    if (pos == n + 1)
        node.next = node.next.next;
    return pos;
}

Meet export conditions

// 获取节点所在位置,逆序
public int length(ListNode node, int n) {
    if (node == null)
        return 0;
    int pos = length(ListNode node, int n) {
                    if (node == null)//exit
                        return 0;/////exit
                    int pos = length(ListNode node, int n) {
                        if (node == null)//exit
                        	 return 0;/////exit
                        int pos = length(node.next, n){...//pos=pos+1	|6
                            if (node == null)//exit
                        		return 0;/////exit
                   			int pos = length(ListNode node, int n) {//	|3.2
                        	if (node == null)//true   					|1
                        		 return 0;/////exit 0 					|2
                                                      } + 1; //pos =0+1 |3.1
                                if (pos == n + 1)//		false			|4
    							    node.next = node.next.next;
    							return pos;				//return 0		|5
                       
                    }+ 1;
                    	.
                        .
                        .
                  }+1
    
    
    
    //获取要删除链表的前一个结点,就可以完成链表的删除
    if (pos == n + 1)
        node.next = node.next.next;
    return pos;
}

Judgment palindrome linked list

ListNode temp;

public boolean isPalindrome(ListNode head) {
    temp = head;
    return check(head);
}

private boolean check(ListNode head) {
    if (head == null)
        return true;
    boolean res = check(head.next) && (temp.val == head.val);
    temp = temp.next;
    return res;
}

open

ListNode temp;

public boolean isPalindrome(ListNode head) {
    temp = head;
    return check(head);
}

private boolean check(ListNode head) {
    if (head == null)
        return true;
    boolean res = check(head.next){
        if (head == null)
            return true;
        boolean res = check(head.next){
            if (head == null)
                return true;
            boolean res = /*check(head.next)*/true && (temp.val == head.val);//reach exit 1
            temp = temp.next;												//下一个 		2
            return res;														//返回上级	   3
        } && (temp.val == head.val);										//判断		4
        temp = temp.next;
        return res;
    } && (temp.val == head.val);
    temp = temp.next;
    return res;
}

Although the recursion of this problem will be calculated repeatedly, it is difficult to think of this recursion because it is understandable