web

# 递归算法

程序调用自身称为递归（ recursion）。普通递归容易造成 栈溢出

# 阶乘例子

//普通递归
function fac(n) {
  if (n === 1) return 1;
  return n * fac(n - 1);
}

fac(5) // 120

解析

这是个阶乘。但是占用内存，因为：

fac(5)
(5*fac(4))
(5*(4*fac(3)))
(5*(4*(3*fac(2))))
(5*(4*(3*(2*fac(1)))))
(5*(4*(3*2)))
(5*(4*(6)))
(5*24)

//120
  • 函数调用会产生“调用记录（存储着函数的相关信息）”存放在栈中，当有函数返回，对应的调用记录才会消失， 上述用普通递归实现的阶乘的执行过程中，不断的调用自身，导致一直没有返回，这样也就不断的在栈中存储调用记录
  • 而当调用自身的次数过多后，就会产生我们常说的“栈溢出”拟人描述： 就想一个人不断地借钱（调用自身，不断向栈中存调用记录），但是总想着以后再还（一直没有返回）， 当外债积累到超出自己偿还能力的时候，就跑路了（栈溢出）
//尾递归
function fac(n, total) {
  if (n === 1) return total;
  return fac(n - 1, n * total);
}

fac(5, 1) // 120

解析

执行过程如下：

fac(5,1)

fac(4,5)

fac(3,20)

fac(2,60)

fac(1,120)

永远只有一个调用记录，调用函数产生一个调用记录，最后一步操作 return fac(n - 1, n * total)，把当前函数的计算结果当做参数传递给了下一个自身调用，这样第一个函数调用产生的调用记录就消失了，因为它执行完了,依次类推，就不会溢出

尾递归：函数的最后一步是执行一个函数

尾递归其实并不是自身的优化？ (opens new window)

# 用js递归的方式写1到100求和

function add(num1,num2){
	var num = num1+num2;
        if(num2+1>100){
	 return num;
	}else{
	  return add(num,num2+1)
        }
 }
var sum =add(1,2);

# 斐波那契数列与递归和迭代

//普通递归
function feibo(n){
		if(n==1||n==2){
			return 1
		}else{
			return feibo(n-1)+feibo(n-2)
		}
	}
feibo(6); //8

//尾调法 
function fb2(n,res1 =1,res2 = 1){
    if(n <= 2){
        return res2;    
    }else{
        return fb2(n-1,res2,res1 + res2);
    }
}

//迭代法
function fb3(n){
    var res1 = 1;
    var res2 = 1;
    var sum = res2;
    for(var i = 2;i < n;i ++){
        sum = res1 + res2;
        res1 = res2;
        res2 = sum;
    }
    return sum;
}

# 使用generator实现斐波那契数列

function* fibonacci() {
  let [prev, curr] = [0, 1];
  for (;;) {
    yield curr;
    [prev, curr] = [curr, prev + curr];
  }
}

for (let n of fibonacci()) {
  if (n > 100000) break;
  console.log(n);
}

# 递归函数被重命名解决方案

可以使用arguments.callee在内侧调用函数，但是如果是严格模式则无效,需要创建一个函数来解决

const factorial = (function f(num) {
  if (num <= 1) {
    return 1;
  } else {
    return num * f(num - 1);
  }
});

# 尾调用

尾调用的概念非常简单，一句话就能说清楚，就是指某个函数的最后一步是调用另一个函数。

以下两种情况，都不属于尾调用。

// 情况一
function f(x){
  let y = g(x);
  return y;
}

// 情况二
function f(x){
  return g(x) + 1;
}

上面代码中，情况一是调用函数g之后，还有别的操作，所以不属于尾调用，即使语义完全一样。情况二也属于调用后还有操作，即使写在一行内。

尾调用不一定出现在函数尾部，只要是最后一步操作即可。

function f(x) {
  if (x > 0) {
    return m(x)
  }
  return n(x);
}
  1. 调用栈：简单地说，调用栈（Call Stack）是一种记录函数地址的栈，当调用一个函数 时，会在调用栈的顶端添加一个新的栈帧（Stack Frame），即入栈；而当函数执行完毕后，就 会将其移出调用栈，即出栈。

在正常情况下，调用栈能够保持有进有出的平衡，但当函数的调用次数激增时（如过多 的递归），调用栈就会消耗大量内存，甚至占满整个内存空间，从而导致栈溢出（Stack Overflow）。不过值得庆幸的是，现代浏览器都不会因为栈溢出而崩溃，其内部已做了限制， 例如，Chrome 仅仅会给出“RangeError: Maximum call stack size exceeded”的错误警告。

  1. 尾调用优化：为了控制栈帧的数量，减少内存空间的使用，引入了尾调用优化（Tail Call Optimization，TCO）。这也不是一个新语法，只是一种空间上的优化，并且所有的工作都由 JavaScript 引擎（如 V8、SpiderMonkey 等）代劳了。

ES6 中的 TCO 只有在严格模式下才能开启，它的原理就是不需要记住尾调用所处函数的 地址。下面是一个检测字符串回文的函数，当开启 TCO 时，由于函数内需要的值已通过参数 的形式传递进来（即不依赖函数外部的变量），因此每次递归都会覆盖前一次函数调用的栈帧， 即调用栈的数量会保持恒定。

"use strict";
function palindrome(str) {
 if (str.length <= 1)
 return true;
 if (str[0] != str[str.length - 1])
 return false;
 return palindrome(str.substr(1, str.length - 2));
}

虽然 TCO 的表现很抢眼，但很遗憾，目前除了 Safrai 之外，大部分浏览器暂不支持，因 此在这些浏览器中还享受不到 TCO 带来的性能提升。

尾调用与尾递归 (opens new window)

# 逆向递归：从树底部选取父级id

<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8" />
		<meta name="viewport" content="width=device-width, initial-scale=1">
		<title></title>
	</head>
	<body>
		dds
	</body>
</html>
<script type="text/javascript">

 const getTreeIds = (tree, nodeId, config) => {
	const { children = 'children', id = 'id' } = config || {}
	const toFlatArray = (tree, parentId) => {
	    return tree.reduce((t, _) => {
	      const child = _[children]
	      return [
	        ...t,
	        parentId ? { ..._, parentId } : _,
	        ...(child && child.length ? toFlatArray(child, _[id]) : [])]
	    }, [])
	  }
	  const getIds = flatArray => {
	      let ids = [nodeId]
	      let child = flatArray.find(_ => _[id] === nodeId)
	      while (child && child.parentId) {
	        ids = [child.parentId, ...ids]
	        child = flatArray.find(_ => _[id] === child.parentId)
	      }
	      return ids
	    }
	return getIds(toFlatArray(tree))
}



const treeData = [
  {
    id: 1,
    label: 'test1',
    children: [
      {
        id: 2,
        label: 'test1-1',
        children: [
          {
            id: 3,
            label: 'test1-1-1'
          },
          {
            id: 4,
            label: 'test1-1-2',
            children: [
              {
                id: 5,
                label: 'test1-1-1-1'
              }
            ]
          }
        ]
      }
    ]
  }
]



console.log(getTreeIds(treeData, 5)) // 输出 [1, 2, 4, 5]
console.log(getTreeIds(treeData, 3)) // 输出 [1, 2, 3]
</script>

# for 循环和递归结合

public getPreval(jsonPath: string, arr: any[]): any | undefined {  
  for (let i = 0; i < arr.length; i++) {  
    if (arr[i].jsonPath == jsonPath) {  
      return arr[i]?.value  
    } else if (arr[i].children && arr[i].children.length > 0) {  
      const result = this.getPreval(jsonPath, arr[i].children)  
      if (result !== undefined) {  
        return result  
      }  
    }  
  }  
  return undefined  
}

参考链接 (opens new window)

最后更新: 11/22/2024, 2:11:53 PM

← valueOf和toString →