递归那点事(上)
# 什么是递归
直接进入正题,什么是递归?——简单来说,递归就是函数内部调用自己。
# 问题
几个简单的面试题,大家可尝试一做,再看我写的参考代码
求1-n的和。(如求1到100的和)
阶乘
数组扁平化,去重,并排序。( [2,[1,2],[0,9,5],[15,[[4]]]] )
斐波那契数列(1,1,2,3,5,8,13...)
问题很简单,多想想多做做就出来了。
# 1.求1-n的和。(如求1到100的和)
function sum (num){
if (num===1) {
return 1
} else {
return sum(num-1) + num
}
}
console.log(sum(100)) //5050
# 2.阶乘
function factorial(x){
if (x===1) {
return 1
} else {
return factorial(x-1) * x
}
}
console.log('factorial',factorial(3))
# 3.数组扁平化,去重,并排序
const arr = [2,[1,2],[0,9,5],[15,[[4]]]]
let result = []
function flat (arr){
arr.forEach(item => {
if (Array.isArray(item)) {
flat(item)
} else {
result.push(item)
}
})
}
flat(arr)
result = [...new Set(result.sort((x,y) => x-y))]
console.log('递归',result) //递归 (7) [0, 1, 2, 4, 5, 9, 15]
上面的方法是用递归的方法实现的,补充一提,可以用数组的方法更简单,如下
const flatArr = [...new Set(arr.flat(3).sort((x,y) => x-y))]
console.log('数组方法flat',flatArr); //数组方法flat (7) [0, 1, 2, 4, 5, 9, 15]
# 4.斐波那契数列
function fibonacci (num){
if (num===0) {
return 0
}else if (num===1) {
return 1
}else {
return fibonacci(num-1) + fibonacci(num-2)
// return arguments.callee(num-1) + arguments.callee(num-2)
}
}
console.log(fibonacci(6)); //8
有细心的朋友,可能会看到我上面的一段注释,用到了arguments.callee
,这就是要引出一个递归的一个相关问题了。
当我们拷贝了这个fibonacci
函数后,又将该fibonacci
函数重新赋值,会报错 fibonacci is not a function
,递归调用失败,如下代码
const copyFibonacci = fibonacci
fibonacci = null
console.log('copyFibonacci',copyFibonacci(6));
原因也很简单,报错信息也很明确指出来了,fibonacci
不是一个函数,因为已经被我们设为null
了。
要解决这一问题,有两种方法
使用
arguments.callee
替代fibonacci
这个名字进行递归调用,如上注释return arguments.callee(num-1) + arguments.callee(num-2)
arguments
指的是实参列表,但是它有一个属性callee
,代表的是所处的函数本身使用命名函数表达式
let fibonacci = function f (num){
if (num===0) {
return 0
}else if (num===1) {
return 1
}else {
return f(num-1) + f(num-2)
}
}
这样无论fibonacci
怎么被赋值改变,函数f
并没有改变,这样就不会报错了。
虽然两种方法都能解决这一问题,但是目前我们推荐使用的是第二种方法
因为方法一中的arguments.callee
在严格模式中不允许使用,在es6后不再有arguments
了,同时其存在一些缺点:
arguments是一个很大的对象,每次调用都要重新创建,影响浏览器性能
递归中的this会不一样,如下代码。(参考 (opens new window))
var global = this;
var sillyFunction = function(recursed) {
if (!recursed) { return arguments.callee(true); }
if (this !== global) {
// 会输出 This is: [object Arguments]
console.log('This is: ' + this);
} else {
console.log('This is the global');
}
}
sillyFunction();
递归有好有坏,其缺点可能有造成栈溢出,导致整个程序崩溃,我们需慎用,具体见下篇。