【算法入门】递归与迭代

简介: 递归与迭代

b288ad75b8225311a858441917197d8.png

前言

作为一个算法萌新,很长一段时间总是对递归迭代的概念含糊不清,只知道用起来都是通过循环执行代码去解决一些问题,但是对于自己用的究竟算递归还是迭代傻傻分不清楚,今天就跟大家一起来好好捋一捋

迭代与递归

概念

  • 迭代

迭代时重复反馈过程的活动,其目的通常是为了接近并到达所需的目标或结果

c5e9bebd311087d2eb1b4756cee5643.png

  • 递归

指在函数的定义中使用函数自身的方法

  • 根据返回值判断
  • 根据操作节点的前后位置(二叉树相关——前序,中序,后序)

f5ca71d003a88f6d722bb81206c9b96.png

这么一看两者的区分还是很明显,通过有没有调用自身,即可判断是递归还是迭代

不过有时突然想起还是容易记混,个人从字面理解的角度出发总结一下:迭代就是一代一代执行下去,很容易与for循环关联起来;递归,归就是回到原来的地方(方法),即再次调用自身

做题

回文链表

234. 回文链表 - 力扣(LeetCode)

给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false

回文指结构数值具有对称性

我们常见判断一个字符串是否是回文字符串,可以使用两个指针,一个最左边一个最右边,两个指针同时往中间靠,判断所指的字符是否相等

  • 迭代解法

首先用迭代的思路我们就需要去遍历链表,并且由于无法取得链表的长度,我们无法使用 for 去遍历,只能用while 通过判断链表节点是否为空完成遍历,取得数值数组后,使用双指针判断数组是否对称来推断是不是回文链表

var isPalindrome = function(head) {
    // 使用迭代获取链表对应的数组
    const list = []
    let root = head
    while (root) {
        list.push(root.val)
        root = root.next
    }
    // 使用双指针判断数组是否对称
    let left = 0
    let right = list.length - 1
    while(left < right) {
        if (list[left] != list[right]) {
            return false
        } else {
            left ++
            right --
        }
    }
    return true
};
复制代码
  • 递归解法

说实话这道题用递归着实不好想,首先要能想到,虽然无法获取链表的长度,但是从后打印链表的数值我们是可以做到的

先看下面的一段代码(从最后开始往前打印)

function reverseLog(head) {
    if (!head) {
        return
    }
    reverseLog(head.next)
    console.log(head.val)
}
复制代码

如果理解了上面的逻辑,那么这道题的递归做法就容易多了

var isPalindrome = function(head) {
    var tmp = head
    function check(head) {
        if (!head) {
            return true
        }
        const res = check(head.next) && (tmp.val == head.val)
        tmp = tmp.next
        return res
    }
    return check(head)
};
相关文章
|
3月前
|
机器学习/深度学习 人工智能 算法
深度学习入门:理解神经网络与反向传播算法
【9月更文挑战第20天】本文将深入浅出地介绍深度学习中的基石—神经网络,以及背后的魔法—反向传播算法。我们将通过直观的例子和简单的数学公式,带你领略这一技术的魅力。无论你是编程新手,还是有一定基础的开发者,这篇文章都将为你打开深度学习的大门,让你对神经网络的工作原理有一个清晰的认识。
|
29天前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
41 2
|
22天前
|
机器学习/深度学习 算法 Python
机器学习入门:理解并实现K-近邻算法
机器学习入门:理解并实现K-近邻算法
30 0
|
2月前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
27 1
|
2月前
|
机器学习/深度学习 算法
机器学习入门(三):K近邻算法原理 | KNN算法原理
机器学习入门(三):K近邻算法原理 | KNN算法原理
|
2月前
|
机器学习/深度学习 算法 大数据
机器学习入门:梯度下降算法(下)
机器学习入门:梯度下降算法(下)
|
2月前
|
机器学习/深度学习 算法 API
机器学习入门(五):KNN概述 | K 近邻算法 API,K值选择问题
机器学习入门(五):KNN概述 | K 近邻算法 API,K值选择问题
|
2月前
|
算法 定位技术
数据结构与算法学习九:学习递归。递归的经典实例:打印问题、阶乘问题、递归-迷宫问题、八皇后问题
本文详细介绍了递归的概念、重要规则、形式,并展示了递归在解决打印问题、阶乘问题、迷宫问题和八皇后问题等经典实例中的应用。
48 0
|
2月前
|
机器学习/深度学习 算法
机器学习入门:梯度下降算法(上)
机器学习入门:梯度下降算法(上)
|
3月前
|
资源调度 算法
基于迭代扩展卡尔曼滤波算法的倒立摆控制系统matlab仿真
本课题研究基于迭代扩展卡尔曼滤波算法的倒立摆控制系统,并对比UKF、EKF、迭代UKF和迭代EKF的控制效果。倒立摆作为典型的非线性系统,适用于评估不同滤波方法的性能。UKF采用无迹变换逼近非线性函数,避免了EKF中的截断误差;EKF则通过泰勒级数展开近似非线性函数;迭代EKF和迭代UKF通过多次迭代提高状态估计精度。系统使用MATLAB 2022a进行仿真和分析,结果显示UKF和迭代UKF在非线性强的系统中表现更佳,但计算复杂度较高;EKF和迭代EKF则更适合维数较高或计算受限的场景。