递归、搜索与回溯——递归

‍♂️个人主页进击的荆棘作者其它专栏《数据结构与算法》《算法》《C起始之路》目录1.总结2.相关题解1.总结在解决一个规模为n的问题时若满足一下条件我们可以使用递归来解决a.问题可以被划分为规模更小的子问题并且这些子问题具有与原问题相同的解决问题。b.当我们知道规模更小的子问题规模为n-1的解时我们可以直接计算出规模为n的问题的解。c.存在一种简单情况或者说当问题的规模足够小时我们可以直接求解问题。一般的递归求解过程如下a.验证是否满足简单情况。b.假设较小规模的问题已经解决解决当前问题。上述步骤可以通过数学归纳法来证明。2.相关题解1汉诺塔问题算法思路这是一道递归方法的经典题目我们可以先从最简单的情况考虑●假设n1只有一个盘子很简单直接把它从A中拿出来移到C上●若n2呢这时候就需要借助B因为小盘子必须在大盘子上面共需要3步为方便叙述记A中的盘子从上到下为1号2号a.1号盘子放到B上b.2号盘子放到C上c.1号盘子放到C上。至此C中的盘子从上到下为1号2号。●若n2呢这时我们需要用到n2时的策略将A上面的两个盘子挪到B上再将最大的盘子挪到C上最后将B上的小盘子挪到C上就完成了所有步骤。当n3时如下因为A中最后处理的是最大的盘子所以再移动过程中不存在大盘子在小盘子上面的情况。则本题可以被解释为1.对于规模为n的问题我们需要将A柱上的n个盘子移动到C柱上。2.规模为n的问题可以被拆分为规模为n-1的子问题a.将A柱上面的n-1个盘子移动到B柱上。b.将A柱上的最大盘子移动到C柱上然后将B柱上的n-1个盘子移动到C柱上。3.当问题的规模变为n1时即只有一个盘子时我们可以直接将其从A柱移动到C柱。●需要注意的是步骤2.b考虑的是总体问题中的子问题b情况。在处理子问题的子问题b时我们应将A柱中最上面的盘子移动到C柱然后再将B柱上的盘子移动到C柱。在处理总体问题的子问题b时A柱中的最大盘子仍然是最上面的盘子因此这种做法是通用的。算法流程递归函数设计void dfs(vectorint a, vectorint b, vectorint c,int n)1.返回值无2.参数三个柱子上的盘子当前需要处理的盘子个数当前问题规模。3.函数作用将A上面的n个盘子挪到C上。递归函数流程1.当前问题规模为n-1时直接将A中的最上面盘子挪动到C中并返回2.递归将A中最上面的n-1个盘子挪动到B中3.将A中最上面的一个盘子挪动到C中4.将B中上面的n-1个盘子挪动到C中。class Solution { public: void hanota(vectorint a, vectorint b, vectorint c) { dfs(a,b,c,a.size()); } void dfs(vectorint a, vectorint b, vectorint c,int n){ //出口 if(n1){ c.push_back(a.back()); a.pop_back(); return ; } //将a上的n-1个盘子借助c移到b上 dfs(a,c,b,n-1); c.push_back(a.back()); a.pop_back(); //将b上的n-1个盘子借助a移到c上 dfs(b,a,c,n-1); } };2.合并两个有序链表算法思路1.递归函数的含义有两链表的头节点把它们合并起来并返回合并后的头节点2.函数体选择两个头节点中较小的节点作为最终合并后的头节点然后将剩下的链表交给递归函数去处理3.递归出口当某一链表尾空时返回另一链表。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { if(!list1) return list2; if(!list2) return list1; if(list1-vallist2-val) { list1-nextmergeTwoLists(list1-next,list2); return list1; } else { list2-nextmergeTwoLists(list1,list2-next); return list2; } } };3.反转链表算法思路1.递归函数的含义交给你一个链表的头指针逆序后返回逆序后的头节点2.函数体先把当前节点之后的链表逆序逆序完之后把当前节点添加到逆序后的链表后面即可3.递归出口当前节点为空或者当前只有一个节点的时候不用逆序直接返回。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { if(!head||!head-next) return head; //将此节点后面的链表逆置 ListNode* newheadreverseList(head-next); head-next-nexthead;//后面的节点指向它 head-nextnullptr;//它指向空方便将逆置后的尾指向空 return newhead; } };4.两两交换链表中的节点算法思路1.递归函数的含义有一链表将这个链表两两交换然后返回交换后的头节点2.函数体先去处理一下第二个节点往后的链表然后再把当前的两个节点交换连接上后面处理后的链表3.递归出口当前节点为空或者当前只有一个节点的时候不要交换直接返回。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* swapPairs(ListNode* head) { if(!head||!head-next) return head; //先把第三个往后的节点交换 ListNode* tmpswapPairs(head-next-next); ListNode* rethead-next; head-nexttmp; ret-nexthead; return ret; } };5.Pow(x, n)算法思路1.递归函数的含义求出x的n次方是多少然后返回2.函数体先求出x的n/2次方是多少然后根据n的奇偶得出x的n次方是多少3.递归出口当n为0的时候返回1即可。class Solution { public: double myPow(double x, int n) { //return n0?dfs(x,-n):dfs(x,n); //当n为无穷小时变成正数时会存不下强转为long long return n0?1.0/dfs(x,-(long long)n):dfs(x,n); } double dfs(double x,long long n){ if(n0) return 1.0; double tmpdfs(x,n/2); return n%20?tmp*tmp:tmp*tmp*x; } };