说一说递归

递归

递归是一个被迫调用过程，当条件不满足时持续调用，是一个直接或间接调用自己的过程。递归的参数根据实际需求的维度去衡量递归的参数设定。

计算机运行和我们人类正常思维差别

程序语言和我们人类的熟知思维过程是不统一的，比如链表对于计算机来说，无论什么时候我们都需要从head进入，然后顺序去查找下一项的值，当它没有调用next的时候他从来不会知道后面的值是谁（因为计算机还没有读到它），但我们人脑不一样，我们有大脑的同时我们还有眼睛帮我们提早分析。

for example

举个例子吧，比如一个链表1->2->3->4,我们现在有个需求是以2项为维度进行翻转（不满足2项不翻转），这样最后的结果应该是2->1->4->3

• 人脑的思维过程:
  我们看一下这个过程，如果我们人脑去想，我们可能会这样认为1，2掉下位置，3，4掉下位置，然后再把他们相连，easy，我们通过眼睛有“一目十行的本事”

• 计算机的分析过程：
  计算器是一个很傻瓜的执行器，虽然它很快吧，但他是完全按照顺序去1，2，3，4这样去做的，我们在顺序的过程中需要知道它如何将程序反转，他们是不会预料到之后的情况，也没有提前看到之后的逻辑"，他们只是去顺序执行

所以我们写递归函数的逻辑时我们需要按照计算机的思维去想问题，以为我们的代码是在计算机上执行，需要我们“换位思考”，毕竟是人家的“地盘”，这就是规则的重要性。下面的东西以链表为例。

一点愚见

我认为递归分为两种形式

• 一种形式是从头到尾执行一遍然后终止输出结果，
• 另一种形式就是分层，我一个数据结构可以拆分成多个递归的过程，从头执行到尾的同时，然后开始向前回溯，每一个递归块的返回值就是下一个递归块的依赖（然后最后返回起始递归块的结果），第二种形式仿佛比第一种多走了一遍。可能说得有点模糊，接下来我们来通过链表好好体会下这个过程

链表举例

链表是通过指针串联排布在内存空间的，他在内存空间的位置是不连续的，所以针对链表的东西至关重要的两个关键要素是解答链表算法的关键，

• 指针，指针是排布成链表的关键
• 关键位置元素缓存。当我们做类似反转的题时，当我们的指针发生了重新指向，那么之前指针的对象元素就断开了，所以我们需要缓存下它，要不然逻辑一运行你就永远找不到它了
  上面两个关键元素应该可以解决大部分链表的问题，接下来看实际例子

1. 反转链表 1->2->3->4->5->null 变成 null->5->4->3->2->1

image.png

解析：我们看见上面这道题我们会发现整个过程逻辑就是完全反转，没有其他额外条件，对于这样的反转无非就是指针的变化，让指针反向就能解决问题。这种问题就是递归的第一种形式，只递归一遍，然后输出最后的结果，所以我们按照就算器的思路去走，按顺序来参数肯定有两个，(pre,cur) (cur, cur.next)...,如此循环，所以递归的过程就只需要考虑终止条件，还有递归过程（就是共同遵循的逻辑），当你return的时候表示递归结束，所以写这种一层递归的时候，我只需考虑前两个参数的逻辑，在考虑最后一次递归的终止条件，这样递归函数就成了.

在做类似设及到第一项变化（包括位置或者增删）的链表，我们最好都设置一个起始变量，包括dump或者啥的，比如反转链表第一项为null，我们就设计为null，这样直接返回pre就行，如果没有null，我们就返回pre.next，扯远了，我们拉回来

1. 考虑前两项变化，这里就是换位
   所以逻辑应该是 cur.next = pre; 但是cur.next之前指针指向第三个数，这下断了，我们递归的时候拿不到他了怎么办？那我们提前先存下！所以let next = cur.next;
   所以变成了 let next = cur.next;cur.next = pre;我们要做到的递归过程逻辑实现了，下次递归无非是cur变成了pre, next变成了cur，如此下去

2. 接下来我们来分析终止条件
   我们的递归的目的只是换位而已，所以针对以pre和cur参数，cur如果为空，我还换个球，所以直接return 上一次的结果吧就是pre嘛。此时pre早已经不是刚传进来的那个pre了，经过我们不需要关心的数次调用，我也不知道它变成啥样了，但我知道终止条件完成后他就是结果

   // 所以根据以上分析，我们把逻辑变成代码就是
   const reverse = (pre, cur) => {
        // 终止条件
        if (!cur) return pre;
        // 递归逻辑
        let next = cur.next;
        cur.next = pre;
        // 下次递归我们不关心，随手写的毕竟是递归过程
       return reverse(cur, next)
        
   }
   以上就是递归函数的写法，但链表反转人家给的只是head参数，无所谓，直接调用咱们自己的函数就行了
   var reverseList = function(head) {
    // 涉及第一个参数的变化咱们需要借个变量
    let temp = null;
    // 只考虑一层的逻辑，所以就是前两个参数
    return reverse(temp, head)
   }
   // 上面为了更好地让大家理解整个流程，其实简单写就可以这样
   var reverseList = function(head) {
    return reverse(null, head)
   }
   
   
   
   

上面是一个简答的问题，接下来我们加大难度，按照每k个一组进行翻转，咱们也就别两个一组进行翻转了，直接上升到k个，这个题在LeetCode上属于hard类型

k个为一组翻转

给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
解析： 这样的题也是翻转问题，这个翻转也和上题一样，但他有附加条件，以k为维度进行翻转，大于k后，再看接下来k项在进行翻转，以此类推，这样的话又分情况，接下来我们屡一下

• 小于k不翻转，直接翻转
• 等于k时翻转，然后翻转后返回结果
• 大于k时，先执行等于k时的结果，剩下的元素再根据情况去相应执行小于k的结果或者大于k的结果，如此反复，当然反复的过程就是大于k的过程，小于k直接就返回了

所以我们思考这中情况下递归如果去疏通逻辑呢，
[图片上传中...(image.png-2da7ec-1587278897727-0)]

*** 递归二要素：终止条件和递归逻辑***

• 先考虑递归的终止条件： 满足k项元素组合执行翻转过程，小于k时不执行翻转，所以递归的终止条件肯定是小于K直接终止。

• 再考虑递归逻辑：其实递归的逻辑主要是考虑大于k时的情况，先进行1-k进行翻转，然后如果K+1以后的项数仍旧大于k项继续执行翻转过程，以此类推，这就是递归过程直到剩余项数小于k时终止
  仔细缕一下思路，递归过程大致清楚了，我们大致知道k项的逻辑了，对于链表图形表示如下

  
  image.png

这时我们需要考虑如何将这种多项进行组合用指针连起来，这种情况我们把每个K项组合作为一个整体，我们递归完了（其实就是所有的数据都被计算机读完了），这种情况下我们指针连线的过程其实就是回溯依赖（当然回溯依赖也可以叫入栈和出栈）的过程，这时最后的块作为前一个块的依赖，并进行组合，然后在传给上一个块，知道回到第一个为止，整个回溯的过程是不是有点像reduce的遍历

image.png

reduce每一项都作为下一个遍历的结果传入
所以这个过程也是这样，例子如下，k为2，我们以k进行分层
1->2->3->4->5
就变成了
1->2 3->4 5 (根据上面的图片)
递归过程
2->1 4->3 5
这时递归到了最后，如果此时递归逻辑下面还有逻辑，比如这样

head.next = swaper(node2);
// 其实逻辑就是相当于
let res = swaper(node2);
// 下面的逻辑就是
head.next = res

这时就是因为head.next = res，递归开始回溯（出栈）了，其实就是reduce的过程，这时我们肯定希望 的过程
起始：5
组合43块：43（为了把它作为整体把箭头省略了） -> 5 组合
变成：435
在和块21组合：21 -> 435
变成：21435（加上省略的箭头就变成）2->1->4->3->5
他们每块的逻辑就相当于reduce下面

image.png

所以我们考虑只需要向前回溯的过程让依赖逐渐连接，然后到顶自然就变成了所求求结果，
如何连接两个块呢，我们需要考虑之前我们做链表题时需要考虑的因素,缓存关键位置项，为了连接，所以我们每个块反转后其实首项变成了末项，所以我们执行逻辑之前先缓存下首项的值，比如let cache = head;我们定义了res = swaper(node2)递归回溯到上一层的结果（再联想下reduce 的return list，其实我们连接本块和依赖块的指针即cache.next = res,也就是我们的递归回溯逻辑
以下是代码

var reverseKGroup = function(head, k) {
    const swaper = (head) => {
        let i = 0;
        let node1 = null,node2 = head;
        let pre = head;
        while(i < k && pre) {
            i++;
            pre = pre.next;
        }
        if (i < k) {
            return head;
        }
        if (i = k) {
            let j = 0;
             while (j<k) {
            j++
            let next = node2.next;
            node2.next = node1;
            node1 = node2;
            node2 = next;
        }
        head.next = swaper(node2)
        return node1;
        }
    }
    return swaper(head)
    
};

文章是刚写的，有点糙，以后再补充完整,有时间写下关于循环的思路😁