做企业网站的研究现状,徐州网站外包,厦门市同安区建设局公开网站,聊城做网站的公司咨询文章目录 递归与栈的关系如何思考递归汉诺塔 经典题目入门#xff1a;斐波那契数列分治法#xff1a;归并排序树的递归遍历组合问题#xff1a;子集搜索问题#xff1a;N皇后 拓展阶乘的迭代法斐波那契数列迭代法青蛙跳 参考文献 掌握递归是解决许多编程问题的关键#xf… 文章目录 递归与栈的关系如何思考递归汉诺塔 经典题目入门斐波那契数列分治法归并排序树的递归遍历组合问题子集搜索问题N皇后 拓展阶乘的迭代法斐波那契数列迭代法青蛙跳 参考文献 掌握递归是解决许多编程问题的关键尤其是那些涉及树形结构、组合问题、搜索问题等领域的题目。递归方法的核心在于将问题分解成更小的子问题直到达到一个基本情况base case然后再逐层返回解决整个问题。理解和掌握递归最好的方式是通过实践一系列逐渐增加难度的问题。
递归与栈的关系
递归的过程就是出入栈的过程
我们以阶乘为例
def Factorial(n):if n 0:return 1return factorial(n-1) * n取 n3则过程如下 第 1~4 步都是入栈过程Factorial(3)调用了Factorial(2)Factorial(2)又接着调用Factorial(1)直到Factorial(0) 第 5 步因 0 是递归结束条件故不再入栈此时栈高度为 4即为我们平时所说的递归深度 第 6~9 步Factorial(0)做完出栈而Factorial(0)做完意味着Factorial(1)也做完同样进行出栈重复下去直到所有的都出栈完毕递归结束。 每一个递归程序都可以把它改写为非递归版本。我们只需利用栈通过入栈和出栈两个操作就可以模拟递归的过程二叉树的遍历无疑是这方面的代表。 如何思考递归
我们怎么判断这个递归计算是否是正确的呢Paul Graham 提到一种方法如下
如果下面这两点是成立的我们就知道这个递归对于所有的 n 都是正确的。· 当 n0,1 时结果正确
· 假设递归对于 n 是正确的同时对于 n1 也正确。这种方法很像数学归纳法也是递归正确的思考方式上述的第 1 点称为基本情况第 2 点称为通用情况。
在递归中我们通常把第 1 点称为终止条件因为这样更容易理解其作用就是终止递归防止递归无限地运行下去。
下面我们用1个例子来具体说明这种数学归纳法
汉诺塔
问题描述为有三根杆子 ABC。A 杆上有 N 个穿孔圆盘盘的尺寸由上到下依次变大BC 杆为空。要求按下列规则将所有圆盘移至 C 杆
每次只能移动一个圆盘大盘不能叠在小盘上面。
问如何移最少要移动多少次
首先看下基本情况即终止条件N1 时直接从 A 移到 C。
再来看下通用情况当有 N 个圆盘在 A 上我们已经找到办法将其移到 C 杠上了我们怎么移动 N1 个圆盘到 C 杠上呢很简单我们首先用将 N 个圆盘移动到 C 上的方法将 N 个圆盘都移动到 B 上然后再把第 N1 个圆盘最后一个移动到 C 上再用同样的方法将在 B 杠上的 N 个圆盘移动到 C 上问题解决。
def Hanoi(n, aA, bB, cC):steps 0if n 0:return stepsif n1:steps 1print(a, --, c)return stepssteps Hanoi(n-1,a,c,b)steps Hanoi(1,a,b,c)steps Hanoi(n-1,b,a,c)return steps经典题目 入门斐波那契数列
斐波那契数列是通过如下递归式定义的
F(0) 0, F(1) 1对于 n 1F(n) F(n-1) F(n-2)
这意味着斐波那契数列从0和1开始之后的每个数字都是前两个数字的和。例如斐波那契数列的前几个数字是0, 1, 1, 2, 3, 5, 8, 13, 21…
def fib(n):if n2:return nreturn fib(n-1) fib(n-2)分治法归并排序
归并排序是一种高效的排序算法基于分治法的一个典型应用。它将一个数组分成两半对每部分递归地应用归并排序然后将两个排序好的部分合并成一个最终的排序数组。
步骤
分解将当前区间一分为二递归地对这两个子区间进行归并排序。合并将两个排序好的子区间合并成一个最终的排序区间。
实现提示 归并过程需要额外的空间来合并两个有序数组这是归并排序空间复杂度为O(n)的原因。 实现归并排序时考虑如何优雅地合并两个有序的子数组。 双指针法
def merge_sort(arr):length len(arr)if length 2:return arrmid length//2left_half arr[:mid]right_half arr[mid:]left_sort merge_sort(left_half)right_sort merge_sort(right_half)i j k 0while i len(left_sort) and j len(right_sort):if left_sort[i] right_sort[j]:arr[k] left_sort[i]i 1k 1else:arr[k] right_sort[j]j 1k 1if i len(left_sort):arr[k:] left_sort[i:]if j len(right_sort):arr[k:] right_sort[j:]return arr 树的递归遍历
关于二叉树的深度优先所有DFS问题我们在前面的文章中有详细的讲解。
前序遍历Preorder Traversal首先访问根节点然后递归地做前序遍历左子树接着递归地做前序遍历右子树。 中序遍历Inorder Traversal首先递归地做中序遍历左子树然后访问根节点最后递归地做中序遍历右子树。 后序遍历Postorder Traversal首先递归地做后序遍历左子树然后递归地做后序遍历右子树最后访问根节点。
在Python中二叉树节点可以通过下面的TreeNode类来表示
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightdef preorderTraversal(root):res []if not root:return resres.append(root)res.extend(preorderTraversal(root.left))res.extend(preorderTraversal(root.right))return resdef inorderTraversal(root):res []if not root:return resres.extend(inorderTraversal(root.left))res.append(root)res.extend(inorderTraversal(root.right))return resdef postorderTraversal(root):res []if not root:return resres.extend(postorderTraversal(root.left))res.extend(postorderTraversal(root.right))res.append(root)return res组合问题子集
给定一组不同的整数返回所有可能的子集幂集。解集不能包含重复的子集。
例子
输入: nums [1,2,3]
输出:
[ [3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]
]这个问题可以通过递归回溯算法来解决。我们之前的文章也讲到过回溯的理论基础和模板。本题的基本思路是遍历所有元素对于每个元素我们可以选择将其包含到当前子集中或者不包含它。每当我们到达数组的末尾时我们就找到了一个可能的子集并将其添加到结果列表中。
def subsets(nums):res []def backtrack(start, path):res.append(path[:])for i in range(start, len(nums)):path.append(nums[i])backtrack(i1, path)path.pop()# returnbacktrack(0, [])return res搜索问题N皇后
N皇后问题简介 N皇后问题要求在一个N×N的棋盘上放置N个皇后使得它们互不攻击。这意味着任何两个皇后都不能处于同一行、同一列或同一对角线上。
解题思路 这个问题可以通过回溯法解决核心思想是逐行放置皇后并在每一行中尝试所有列直到找到一个合法的位置。我们需要一个方法来检查在放置每个新的皇后时棋盘的状态是否仍然合法。 def solveNQueens(n):board [[.] * n for _ in range(n)]res []def isValid(board, row, col):for i in range(row):# 检查列是否合法if board[i][col] Q:return False# 检查左上对角线if col - i - 1 0 and board[row - i - 1][col - i - 1] Q:return False# 检查右上对角线if col i 1 n and board[row - i - 1][col i 1] Q:return Falsereturn Truedef backtrack(board, row):if row n:res.append([.join(row) for row in board])returnfor col in range(n):if not isValid(board, row, col):continueboard[row][col] Qbacktrack(board, row 1)board[row][col] .backtrack(board, 0)return res拓展
迭代法可以避免递归并且在实际应用中迭代通常比递归有更好的性能尤其是在防止栈溢出方面。
阶乘的迭代法
def factorial(n):if n 0:return 1pre 1for i in range(2, n1):result i * prepre resultreturn result斐波那契数列迭代法
def fib(n):if n0:return 0if n1:return 1pre_n_1 1pre_n_2 0for i in range(2,n1):result pre_n_1 pre_n_2pre_n_2 pre_n_1pre_n_1 resultreturn result青蛙跳
一只青蛙可以一次跳 1 级台阶或者一次跳 2 级台阶例如
跳上第 1 级台阶只有一种跳法直接跳 1 级即可。 跳上第 2 级台阶有两种跳法每次跳 1 级跳两次或者一次跳 2 级。 问要跳上第 n 级台阶有多少种跳法
递归法
def jump(n):if n 2:return nreturn jump(n - 1) jump(n - 2)迭代法
def jump(n):if n 2:return npre_n_1 2pre_n_2 1for i in range(3,n1):result pre_n_1 pre_n_2pre_n_2 pre_n_1pre_n_1 resultreturn result参考文献
一文读懂递归算法 一文看懂什么是递归
