首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法--递归

算法--递归

作者头像
奋飛
发布2019-08-15 16:46:06
4870
发布2019-08-15 16:46:06
举报
文章被收录于专栏:Super 前端Super 前端

版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://ligang.blog.csdn.net/article/details/83757651

递归

函数直接或间接调用函数本身。递归是一种计算过程,如果其中每一步都要用到前一步或前几步的结果,称为递归的。用递归过程定义的函数,称为递归函数。它解决问题的各个小部分,直到解决最初的大问题。

  • 有限次(必须有出口)可预见性结果中,找到结果与上一次结果之间的关系;
  • 关键在于梳理清楚本次结果和上一次结果的关系有哪些方面或是因素;
  • 在算法的分析中,当一个算法中包含递归调用时,其时间复杂度的分析会转化成为一个递归方程的求解。

经典递归案例:

示例: 斐波那契数列:1、1、2、3、5、8、13、21、34

F(0) = 0; F(1) = 1; F(n) = F(n-1) + F(n-2)

function fibonacci(n) {
  if(n === 0 || n === 1) {
    return 1
  }
  return fibonacci(n - 1) + fibonacci(n - 2)
}
let fibonacci = (function() {
  let memory = []
  return function(n) {
    return memory[n] = (n === 0 || n === 1) ? 1 : fibonacci(n - 1) + fibonacci(n - 2)
  }
})()

示例: 最大公约数,采用辗转相除法(欧几里得算法)

定理:两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

gcd(a, b) = gcd(a, a mod b)

function gcd (a, b) {  
    if (a < b) {
        [a, b] = [b, a]
    }
    if (a % b === 0) {
        return b
    }
    return gcd(b, a % b)
}

其他方式:分解质因数、短除法、更相减损法等

示例:

var menu = {
	children: [{
        path: '/a',
        name: 'a',
        meta: {name: 'a'},
        children: [{
            path: 'a1',
            name: 'a1',
            meta: {name: 'a1'},
            children: [{
                id: 'a11',
                path: 'a11',
                name: 'a11',
                meta: {name: 'a11'},
            }, {
                path: 'a12',
                name: 'a12',
                meta: {name: 'a12'},
            }]
        }, {
            path: 'a2',
            name: 'a2',
            meta: {name: 'a2'},
        }]
    }, {
        path: '/b',
        name: 'b',
        meta: {name: 'b'}
    }]
}

/**
 * @param menu 菜单数据
 * @param name 查询的节点名称
 */
function getMenuByName (menu, name) {
    if (menu.name === name) {
        return menu
    }
    let childrens = menu.children
    if (childrens && Array.isArray(childrens)) {
        for(let item of childrens) {
            let result = getMenuByName(item, name)
            if(result) return result
        }
    }
}

示例:递归DOM

function getElementById(node, id) {
    if (!node) return null
    if (node.id === id) return node
    for (var i = 0, len = node.childNodes.length; i < len; i++) {
        var found = getElementById(node.childNodes[i], id)
        if (found) return found
    }
    return null
}
getElementById(document, 'abc')

注意:

  • 在写递归时,需要先考虑边界条件,否则会导致栈溢出(RangeError: Maximum call stack size exceeded)
  • ECMAScript 6有尾调用优化。如果函数内最后一个操作是调用函数,会通过“跳转指令”而不是“子程序调用”来控制!
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018年11月05日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 递归
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档