深入浅出递归算法

2024-10-09 16:42:20 浏览数 (4)

递归思想

递归就是将一个很大的问题拆分成子问题，然后再将子问题继续拆分，拆分成更小的子问题，最后直到不能拆分为止。 递归一共分为三个步骤，首先，我们要将一个问题拆为一些子问题，然后去看这些子问题是否有相同的方法可以继续拆分，所以递归的关键就是一个大问题是否能转换成相同类型的子问题，然后子问题是否又能继续转换成相同类型的子问题，注意这里我们就需要搞定我们这个递归的函数传递的参数具体需要什么，也就是（函数头），当我们确立了子问题之后，我们就需要进行函数体的书写了，书写函数体主要围绕单个子问题进行，因为，我们的一个大的问题都可以拆分为一个个的小的子问题，所以这些子问题都可以通过一个方法来处理，所以只需要对一个子问题进行书写函数体就行了，最后，我们需要防止无限递归，也就是递归的终止条件，向上归的过程。

总结：递归的方法

  1. 找到类型相同的子问题
  2. 对某个子问题进行函数体方法的书写
  3. 递归的出口----终止条件的判断

递归的题目

1.汉诺塔问题

问题分析

这里是引用这里是引用

输入和输入：

首先我们来分析： 1.找到子问题

可以看到子问题很容易就出来了，我们不管有多少个盘子，我们都可以将上面的n-1个盘子看成一个整体，然后将上面n-1个盘子借助C移到B柱上，然后将最下面的盘子移到C上，然后再对上面n-1个盘子实行相同的方法，对上面n-1个盘子上的n-2个盘子用刚刚一样的方法。

这里子问题找到了，我们就可以确定我们的函数头和传递的参数了，对于上面的图我们传递的函数头就可以用下面类似方式写出：dfs(A,B,C,n). 2.用单个子问题寻找函数体 单个子问题是：

首先第一步是：dfs(A,C,B,n-1)

这句代码的意思是将A柱上n-1个盘子从A移到B上，借助C

第二部是：A.back()->C（伪代码）

将A上最后一个盘子移到C，当我进行了第一步递归之后，只剩下最后一个盘子了，所以，我需要将最后一个盘子移到C上

第三部：dfs(B,A,C,n-1)

将B柱上剩下的盘子移到C上，注意中间的过程我们不需要管，他会不断拆分，我们只需要找到同一的方法即可

3.递归出口 对于递归的出口，我们可以看上面的子问题，当我们只有一个盘子的时候我们就直降将这个盘子移到C柱上了，所以这里的最后的递归出口就是当只有一个盘子的时候。

代码展示
代码语言：javascript复制
class Solution {
public:
    void dfs(vector<int>& x,vector<int>&y,vector<int>&z,int n)
    {
        if(n==1)//当只有一个盘子的时候移到z柱上
        {
            //移到z柱上
            z.push_back(x.back());
            //将x柱上的值删除
            x.pop_back();
            return;
        }
        //将x柱上的整体的n-1个盘子整体移到y柱上
        dfs(x,z,y,n-1);
        //然后将x柱上剩下的一个盘子移动到z柱上
        z.push_back(x.back());
        x.pop_back();
        //最后将y柱上的剩下的盘子移动到z柱上即可，借助x柱，注意：y柱上有n-1个盘子
        dfs(y,x,z,n-1);
    }
    void hanota(vector<int>& a, vector<int>& b, vector<int>& c)
    {
        dfs(a,b,c,a.size());
    }
};

2.合并两个有序链表

样例输入和输出：

问题分析

1.寻找子问题 这里其实我们可以选一个小的作为头，选好这个头之后将这个头去指向这个函数头，这个函数头就是去给我们合并的函数。 确定函数头：dfs(l1,l2) 2.根据单个子问题找到函数体

这里我们可以通过子问题找到函数体：首先函数头是传递两个链表的头，然后返回的是新的头结点，所以这里我们只需要取两个链表的中的小的为新的头，然后去链接剩下的两个链表

函数体：min->next=dfs(min->next,other)

这里大致就可以将函数体写成这样，小的链表的头指向小的链表的剩下的部分和另一个链表

3.递归出口 递归出口：当有一个函数为空时直接返回另一个链表，注意：这里其实可以这样想，当我们链接当一个链表为空的时候是不是另一个链表链接上去肯定是有序的，所以这里我们只需要返回另一个部位空的链表即可。

代码展示
代码语言：javascript复制
class Solution 
{
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        if(list1==nullptr)return list2;
        if(list2==nullptr)return list1;
        if(list1->val<=list2->val)
        {
            list1->next=mergeTwoLists(list1->next,list2);//list1作为头结点合并list1->next,和list2
            return list1;
        }
        else
        {
            list2->next=mergeTwoLists(list1,list2->next);//连接list2->next和list1
            return list2;
        }
    }
};

3.反转链表

问题分析

这道题我们其实也可以用递归来做，我们要将整个链表翻转其实可以看做将1后面的链表翻转，剩下的链表翻转又可以分解成剩下的链表的剩下的部分翻转，接下来我用一个图方便理解

大概就是上图的意思，我们先深度优先遍历到最后一个节点，然后再向上翻转注意，这里我没有志向nullptr，但是我们每次翻转的时候都要指向nullptr，这是为了递归的统一。

函数头 函数头：dfs(head)

函数体

函数体：newhead=reverseList(head->next); 我们只需要创一个新的头来等于剩下的翻转过的链表，注意：这里我们翻转过的链表是抽象的递归，具体是怎么完成的计算机会完成，我们只需要给出方法，这里我们已经得到了翻转链表的方法之后，我们就可以直接将就的head与翻转过的链表进行连接即可。

递归出口 当当前节点指向的下一个是nullptr的时候或者当当前节点是nullptr的时候就直接返回当前节点。

代码展示
代码语言：javascript复制
class Solution 
{
public:
    ListNode* reverseList(ListNode* head) 
    {
        //出口
        if(head==nullptr||head->next==nullptr)
        {
            return head;
        }
        ListNode*newhead=reverseList(head->next);
        //原本head->next是head的next但是现在要反转过来
        //就要把head的next节点指向自己就是head->next->next=head;
        head->next->next=head;
        head->next=nullptr;
        return newhead;
    }
};

4.两两交换 链表中的节点

问题分析

这里这道题和上一道题其实很相似，我们其实只需要将后面所有应该交换的节点全部交换了，然后将后面节点的新的头给前面两个节点连接上即可，注意这里后面是怎么交换的我们也不知道，但是我们用一个函数去让他交换，我们让他交换前两个节点后面剩下的节点，它会转换成叫唤后面剩下的节点除了前两个节点外的剩下的节点，这样一直递归下去，直到遇到递归出口为止。

函数头 函数头：dfs(head)

函数体 注意这里我们返回的交换之后链表的新的头，意思就是当我们把除了1和2节点外的所有节点外的节点交换之后，会返回一个新的节点，注意看上面给出的示例，意思就是当我们用一个递归表示的话，返回的就是4这个节点，所以我们可以直接用tmp存储这个节点，然后将前面两个节点的指向进行变化即可。 函数体：

代码语言：javascript复制
ListNode*tmp=swapPairs(head->next->next);
auto next=head->next;
head->next->next=head;
head->next=tmp;

递归出口 这里的递归出口还是当遇到空节点或者下一个节点是空节点直接返回当前节点

代码展示
代码语言：javascript复制
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head==nullptr||head->next==nullptr)
        {
            return head;
        }
        ListNode*tmp=swapPairs(head->next->next);
        
        auto next=head->next;
        head->next->next=head;
        head->next=tmp;
        return next;
    }
};

总结

递归算法作为计算机科学中的一种基本思想，展现了其简洁优雅和强大的解决问题能力。从数学计算到复杂的数据结构处理，递归提供了一种自然且直观的方法来分解和解决问题。尽管递归在某些情况下可能带来性能和资源上的挑战，但通过优化技术如记忆化存储和尾递归优化，我们可以克服这些困难，实现高效的递归算法。

递归不仅仅是编程技术，更是一种思维方式。通过理解递归的本质，我们能够培养出更好的抽象思维能力，解决更复杂的计算问题。希望这篇博客能够帮助你更好地理解递归算法，并激发你在编程中更多地应用和探索这一强大的工具。

无论你是编程新手还是经验丰富的开发者，掌握递归算法都会为你提供一种新的视角，帮助你在算法和数据结构的学习和应用中取得更大的进步。让我们一起拥抱递归的美妙世界，不断挑战和提升自我！

递归 函数 链表 连接 算法

0 人点赞