算法---递归

心已赠人 2021-09-23 18:46 371阅读 0赞

# 1、什么是递归？ #

“要理解递归，就得先了解什么是递归”，实际上这句话就是一个递归。哈哈，是不是把大家说蒙了，没关系，接下来举个从小就听 过的例子：从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山…  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]

# 2、举例数组求和----计算数组某个区间内所有谁的和 #

package recursion;
    
    public class Sum { 
        public static int sum(int[] arr) { 
            return sum(arr, 0);
        }
    
        private static int sum(int[] arr, int index) { 
            if (index == arr.length) { 
                return 0;
            }
            return arr[index] + sum(arr, index + 1);
        }
    
        public static void main(String[] args) { 
            int[] nums = { 1, 2, 3, 4, 5, 6, 7, 8};
            System.out.println(sum(nums));
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 1]

# 3、链表具有天然的递归性 #

对于一个链表来说，我们可以理解成一个一个节点的挂接，也可以理解成是一个头节点后面又挂接了一个更小的更短的链表。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 2]

# 4、解决链表中删除元素的问题 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 3]

## 删除链表中等于给定值 val 的所有节点 ##

public class ListNode { 
        int val;
        ListNode next;
    
        ListNode(int x) { 
            val = x;
        }
    
    }
    -------------------------------------------------------------------
    class Solution3 { 
        public ListNode removeElements(ListNode head, int val) { 
    
            if (head == null) { 
                return null;
            }
            ListNode res = removeElements(head.next, val);
            if (head.val == val) { 
                return res;
            } else { 
                head.next = res;
                return head;
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]: /images/20210923/f0e1708566714f92899554cf3aa10c6c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 1]: /images/20210923/411c2fe022bc48cfb839bb1a021c0c10.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 2]: /images/20210923/f0d66af09812491bb9947d8580564470.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 3]: /images/20210923/41c773f1176442c4ae3d28e4fd9aad67.png