递归算法和回溯算法

一.递归算法

1.什么是递归

递归是一种在计算机科学和数学中广泛使用的重要概念，它指的是一个函数或算法直接或间接地调用自身来解决问题的方法。

在二叉树的前中后序遍历中,我们也经常使用递归实现

2.核心思想

递归将复杂问题分解为更小的、相似的子问题，通过解决这些子问题最终解决原始问题。递归包含两个关键部分

3.递归的特点

int factorial_recursive(int n) { //递归结束条件 if (n == 0 || n == 1) { return 1; } else { //递归处理逻辑 return n * factorial_recursive(n - 1); } }

int fibonacci_recursive_basic(int n) { //递归结束条件 if (n <= 0) return 0; if (n == 1||n==2) return 1; //递归处理逻辑 return fibonacci_recursive_basic(n - 1) + fibonacci_recursive_basic(n - 2); }

(2)缺点:

• 可能产生大量函数调用，占用栈空间(递归深度过大也会导致程序崩溃)

• 可能存在重复计算（如朴素斐波那契递归）

• 调试可能比较困难

二.回溯算法

说完了递归,就不得不提到递归的一个使用--回溯算法了

1.什么是回溯算法:

回溯算法是一种通过试错来寻找问题解决方案的算法。它采用深度优先搜索的策略，在搜索过程中逐步构建解决方案，当发现当前路径不可能得到正确解时，会回溯（退回）到上一步，尝试其他可能性。

而由于其退回到上一步的特点,非常适合使用递归来实现

2.核心特点:

• 系统性搜索：尝试所有可能的解决方案

• 递归实现：通常用递归实现，每层递归做一个选择

• 剪枝优化：在发现当前路径不可能成功时提前终止

• 状态恢复：回溯时需要撤销当前选择，恢复状态

3.回溯算法的使用:

在二叉树中,常用于按需要寻找二叉树的路径

力扣257.二叉树的所有路径

给你一个二叉树的根节点root，按任意顺序，返回所有从根节点到叶子节点的路径。

思路:

每次遍历到叶子节点,将该路径拼接完成后,删除路径数组中最后一个元素,相当于回到其父节点,进行另一条路径的搜索

代码实现:

class Solution { public: //回溯算法的实现 void func(TreeNode* root,vector<int>&path,vector<string>&ans){ //每次将当前节点放入数组中 path.push_back(root->val); //判断是不是叶子节点,如果是就进行处理 if(root->left==nullptr&&root->right==nullptr){ //拼接路径 string s = to_string(path[0]); for(int i = 1;i<path.size();i++){ s+="->"; s+=to_string(path[i]); } //将其放入结果数组中 ans.push_back(s); } //递归调用,若左(右)子树存在,将其传入参数 if(root->left){ func(root->left,path,ans); //!!核心!! //回溯算法,每次拼接路径完成后,将最后一个叶子节点删除 //相当于退回到该叶子节点的父节点进行另一条路径的搜索 path.pop_back(); } if(root->right){ func(root->right,path,ans); path.pop_back(); } } vector<string> binaryTreePaths(TreeNode* root) { vector<int>path; vector<string>ans; func(root,path,ans); return ans; } };

力扣112.路径总和

给你二叉树的根节点root和一个表示目标和的整数targetSum。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和targetSum。如果存在，返回true；否则，返回false。

代码实现:

class Solution { public: void func(TreeNode* root,vector<int>&path,vector<int>&ans){ //递归结束条件 if(root==nullptr)return; //递归处理逻辑 path.push_back(root->val); //如果是叶子节点,就计算路径总和 if(root->left==nullptr&&root->right==nullptr){ int sum = 0; for(int i = 0;i<path.size();i++){ sum+=path[i]; } ans.push_back(sum); } //递归传入其左节点或右节点 if(root->left){ func(root->left,path,ans); //和上题一样,回溯算法的使用 path.pop_back(); } if(root->right){ func(root->right,path,ans); path.pop_back(); } } bool hasPathSum(TreeNode* root, int targetSum) { vector<int>path; vector<int>ans; func(root,path,ans); //将所有路径总和相加,判断是否和目标值相等 for(int i = 0;i<ans.size();i++){ if(ans[i]==targetSum){ return true; } } return false; } };

像力扣129也是属于使用回溯算法记录每条路径,再进行相应的操作,这里就不一一列举了

4.回溯算法优缺点:

优点:

(1)系统性：能穷举所有可能的解决方案

(2)通用性强：适用于多种类型的问题

(3)容易理解和实现：框架清晰，逻辑简单

(4)能保证找到解：如果解存在，一定能找到

缺点:

(1)时间复杂度高：通常是指数级或阶乘级复杂度

(2)可能效率低下：对于大规模问题不适用

(3)需要剪枝优化：否则效率极低

三.总结:

1. 递归与回溯的关系

• 递归是基础：回溯算法通常用递归实现，递归提供了回溯所需的"返回上一层"的能力

• 回溯是应用：回溯是递归的一种特定应用场景，专注于"试错-返回"的搜索策略

2.核心区别

3. 关键要点

1. 递归三要素：

   • 明确的递归结束条件

   • 将问题分解为子问题

   • 递归调用解决子问题

2. 回溯四要素：

   • 路径：已经做出的选择

   • 选择列表：当前可以做的选择

   • 结束条件：达到决策树底层，无法再做选择

   • 撤销选择：回溯的核心，回到上一步

3. 优化技巧：

   • 递归优化：记忆化、尾递归优化、迭代改写

   • 回溯优化：剪枝、提前终止无效搜索、状态压缩