[TOC] # 简介 本质上,将原来的问题,转化为更小的同一问题 举例 `Sum(arr[0...n-1]) = arr[0] + Sum(arr[1...n-1])`更小的同一问题 `Sum(arr[1...n-1]) = arr[1] + Sum(arr[2...n-1])`更小的问题 `Sum(arr[n-1...n-1]) = arr[n-1] + Sum([])` 最基本的问题 # 代码 ~~~ public class Sum { public static int sum(int[] arr) { return sum(arr, 0); } //计算arr[l...n)这个区间内所有数字的和 private static int sum(int[] arr, int l) { //当初始值和我们这个数组的长度相等的时候,表示已经到了边界了 if (l == arr.length) { return 0; } return arr[l] + sum(arr, l + 1); } //测试下 public static void main(String[] args) { int[] nums = {1, 2, 3, 4, 5, 6}; System.out.println(sum(nums)); } } ~~~ # 分析 1. 有求解的最基本问题,需要我们自己写 2. 把原问题转化为更小的问题(核心)  注意递归函数的宏观语义 递归函数就是一个函数,完成一个功能 # 链表天然的递归性  ## 问题 摘取leetcode https://leetcode-cn.com/problems/remove-linked-list-elements/description/ 删除链表中等于给定值 val 的所有元素。 示例 给定: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6 返回: 1 --> 2 --> 3 --> 4 --> 5 我们再看下leetcode的这个问题  ## 代码 ~~~ public class Solution { public ListNode removeElements(ListNode head, int val) { //当递归到头节点为null,表示链表已经被查完了 if (head == null) { return null; } // ListNode res = removeElements(head.next, val); // //head也满足被删除的条件 // if (head.val == val) { // //表示head后面的元素满足条件 // return res; // } else { // //这边表示head不要删除 // head.next = res; // //就把head那边满足条件的返回 // return head; // } //简写 head.next = removeElements(head.next, val); return head.val == val ? head.next : head; } } ~~~ ## 分析  ## 总结 递归调用是有代价的:函数调用+系统栈空间