什么是递归

时间:2021-09-02 01:19:56

参考文章:426,什么是递归,通过这篇文章,让你彻底搞懂递归 (qq.com)

什么是递归

递归,就是在运行的过程中调用自己

构成递归需要具备的条件:

     1,子问题要与原始问题为同样的事,且更为简单

     2,不能无限制地调用自身,要有个出口,化简为非递归状况处理

递归模板

public void recursion(参数0) {    if (终止条件) {        return;    }    recursion(参数1);}

终止条件要在递归最开始的地方,要不然就出不来了

递归示例

什么是递归

 分支污染问题

递归的时候如果处理不当可能会出现分支污染导致结果错误

比如多个分支使用同一个数据结构,对同一个数据结构进行修改等,就会互相影响

解决办法:

每个分支重新创建要使用的数据结构

我们知道当执行完分支1的时候,list中会携带分支1的数据,当执行分支2的时候,实际上我们是不需要分支1的数据的,所以有一种方式就是从分支1执行到分支2的时候要把分支1的数据给删除,这就是大家经常提到的回溯算法

什么是递归

递归反转链表

什么是递归

 

/**
 * 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 == nullptr || head->next == nullptr )
      {
        return head;
      }
    ListNode* newhead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newhead;
    }
};

看着简单,理解也不难。动手就忘光了