专栏首页达摩兵的技术空间算法之递归(js版本)

算法之递归(js版本)

递归

相信在数学中很常见这个概念,实际在编程中也很常见这样的思维。递归通俗的来说,就是通过不断的将当前问题进行分解,向前追溯直到终点然后再反推求解的过程。

通俗解读

案例一 :看电影不知道在第几排

看电影时不清楚自己在第几排,可以通过问前一排的人来得知,进行加1即可。那么用递归的思路求解代码就是这样的。

function fn = (n) {
    if(n< = 0) return '座位不存在'
    if(n>1) {
    return fn(n-1)+1
    } else {
    return 1
    }
}

案例二 :走格子有多少走法

一共有n格,每步可以走1格或者2格,问一共有多少走法。 首先分解问题是第n格可以是前面n-1格走的,也可能是n-2格走的。所以fn(n) = f(n-1) + f(n-2)。也要知道终止条件是只有1步,那么只有一步的可能情况是还有1格,也可能是还有2格。

function fn = (n){
  if(n>2){
return fn(n-1) + fn(n-2)
} else if(n==2)   {
return 2
} else {
return 1
}
}

核心要点解析

可以分解为子问题

也就是返回的递归子问题与当前问题的逻辑拆解关系

这个问题与分解之后的子问题,除了数据规模不同,其他都是相同的

也就是子问题的解法与当前问题是完全一致的,不需要区别写法

有终止条件

不再进行递归的判断条件,并且知道临界条件的特殊值是可求的

实际问题

堆栈溢出

当递归层级过深的时候,因为在递归的过程中会一直把临时变量封装为栈压入内存栈,如果一直压入,就会导致溢出导致服务崩溃。通常的解决方案是设置一个递归深度来进行限制。 比如下面的代码:则假定内存深度为1000,超过1000则抛出异常。

let depth = 0 
let f = (n) => {
++depth
if(depth>1000) throw error()
if(n===1) return 1
return fn(n-1) + 1 
}

说明:这种不是很实用,因为内存一般是动态变化的,用定值没意义,而如果动态获取内存,又小题大做了。

重复计算

还是上面的递归计算走法的案例,不难发现会重复计算一些中间步骤的走法,导致浪费。当然这种问题不一定会有,和问题的分解有关。

优化方式是针对已经得到结果的走法计到Map缓存中直接使用。

let  f  = ( n) => {
  if (n == 1) return 1;
  if (n == 2) return 2;
  // hasSolvedList 可以理解成一个 Map,key 是 n,value 是 f(n)
  if (hasSolvedList.containsKey(n)) {
    return hasSovledList.get(n);
  }
  ley ret = f(n-1) + f(n-2);
  hasSovledList.put(n, ret);
  return ret;
}

无限递归

也就是没有办法找到终止条件的情况要考虑进,主要是避免死循环或者脏数据的影响

总结

本文主要介绍了常见的递归案例,可以用递归的核心点以及递归可能存在的问题。

彩蛋~~ 魔法币挑战

小易准备去魔法王国采购魔法神器,购买魔法神器需要使用魔法币,但是小易现在一枚魔法币都没有,但是小易有两台魔法机器可以通过投入x(x可以为0)个魔法币产生更多的魔法币。 魔法机器1:如果投入x个魔法币,魔法机器会将其变为2x+1个魔法币 魔法机器2:如果投入x个魔法币,魔法机器会将其变为2x+2个魔法币 小易采购魔法神器总共需要n个魔法币,所以小易只能通过两台魔法机器产生恰好n个魔法币,小易需要你帮他设计一个投入方案使他最后恰好拥有n个魔法币

如果你对这项游戏的解法有兴趣,就请跳转下面的链接介绍吧,有代码有真相。

  • 魔法币递归通关

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 当JSON.parse”遇上”非键值对

    在json大行其道并作为前后端主要通讯的数据格式之一时,对json本身的使用和了解多少人都会有些概念,当然随之而来的也是对json的对象以及其字符串形式的互相转...

    RobinsonZhang
  • 网易递归编程题,魔法币

    输入描述: 输入包括一行,包括一个正整数n(1 ≤ n ≤ 10^9),表示小易需要的魔法币数量。

    RobinsonZhang
  • 以jq为案例查看外观模式

    套餐服务–外观模式,属于大类结构型设计模式的一种,通常是为一组复杂的子系统接口提供一个更高级的统一接口,通过这个接口让使用者对子系统的接口更加容易访问。

    RobinsonZhang
  • 【编程经验】宏定义

    预处理命令可以改变程序设计环境,提高编程效率,它们并不是 C 语言本身的组成部分,不能直接对它们进行编译,必须在对程序进行编译之前,先对程序中这些特殊的命令进行...

    编程范 源代码公司
  • Netty 系列七(那些开箱即用的 ChannelHandler).

        Netty 为许多通用协议提供了编解码器和处理器,几乎可以开箱即用, 这减少了你在那些相当繁琐的事务上本来会花费的时间与精力。另外,这篇文章中,就不涉及...

    JMCui
  • LeetCode 520. 检测大写字母

    全部字母都是大写,比如"USA"。 单词中所有字母都不是大写,比如"leetcode"。 如果单词不只含有一个字母,只有首字母大写, 比如 “Google”...

    Michael阿明
  • 【学习】服装调研报告之2:品牌表现及价值数据分析

    目前国内休闲服饰品牌众多,在服装市场调研中过程中,了解消费者购买习惯是基础,据此制定相应的市场运营计划,但若想在众多品牌中脱颖而出还需要不断的努力。我们必须熟知...

    小莹莹
  • Cocoapods生成静态库(完整)

    程序员不务正业
  • 再获D轮10亿元融资!看钱大妈如何玩转生鲜市场?

    钱大妈是广州钱大妈农产品有限公司旗下一家专注于生鲜肉菜市场的连锁服务商,推行“不卖隔夜肉”价值主张和B2B新型供应链模式,致力于打造生鲜社区O2O服务。从最开始...

    码农架构
  • 【业界】人工智能如何帮助加密货币交易者实现收益最大化?

    加密货币交易是有风险的,当你对缺乏数据、虚假宣传和其他因素投入时,可能会导致重大损失。Signal是一个新的平台,旨在通过机器学习解决这个问题。 ? 交易加密货...

    AiTechYun

扫码关注云+社区

领取腾讯云代金券