# Recursion

Straight to the point, what is recursion—— To put it simply, recursion is a function that calls itself internally.

A few simple interview questions, you can try to do, and then look at the reference code I wrote

1. Find the sum of 1-n. (if the sum of 1 to 100 is required)

2. Factorial

3. Flatten, de duplicate and sort the array. ( [2,[1,2],[0,9,5],[15,[]]] )

4. Fibonacci series

The problem is very simple. Think more and do more.

1. Find the sum of 1-n. (if the sum of 1 to 100 is required)

```function sum (num){
if (num===1) {
return 1
} else {
return sum(num-1) + num
}
}
console.log(sum(100))   //5050```

2. Factorial

```function factorial(x){
if (x===1) {
return 1
} else {
return factorial(x-1) * x
}
}
console.log('factorial',factorial(3))```

3. Flatten, de duplicate, and sort the array

`const arr = [2,[1,2],[0,9,5],[15,[]]]`
```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('recursion',result)  //recursion (7) [0, 1, 2, 4, 5, 9, 15 ```

The above method is implemented by recursive method. In addition, it can be simpler to use array method, as follows

```const flatArr = [...new Set(arr.flat(3).sort((x,y) => x-y))]
console.log('Array method flat',flatArr);    //Array method flat (7) [0, 1, 2, 4, 5, 9, 15]```

4. Fibonacci series

```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

If you have careful friends, you may see a comment above me, which uses arguments Callee, this is to lead to a related problem of recursion.

When we copy the fibonacci function and re assign the value of the fibonacci function, the error "fibonacci is not a function" will be reported, and the recursive call fails, as shown in the following code

```const copyFibonacci = fibonacci
fibonacci = null
console.log('copyFibonacci',copyFibonacci(6));```

The reason is also very simple. The error message is also clearly pointed out. fibonacci is not a function because it has been set to null by us.

There are two ways to solve this problem

1. Use arguments Callee is called recursively instead of fibonacci, as noted above

`return arguments.callee(num-1) + arguments.callee(num-2)`

arguments refers to the argument list, but it has an attribute callee, which represents the function itself

2. Use named function expressions

```let fibonacci = function f (num){
if (num===0) {
return 0
}else if (num===1) {
return 1
}else {
return f(num-1) + f(num-2)
}
}```

In this way, no matter how fibonacci is changed, the function f does not change, so there will be no error.

Although both methods can solve this problem, we recommend the second method at present, because the arguments in method 1 Callee is not allowed in strict mode.

At the same time, it has some disadvantages:

1.arguments is a large object, which needs to be recreated every time it is called, which affects the performance of the browser
2. this in recursion will be different, as shown in the following code. (reference from: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Functions/arguments/callee )
```var global = this;
var sillyFunction = function(recursed) {
if (!recursed) { return arguments.callee(true); }
if (this !== global) {
// Will output This is: [object Arguments]
console.log('This is: ' + this);
} else {
console.log('This is the global');
}
}
sillyFunction();```

Tags: recursion

Posted by tomkleijkers on Fri, 20 May 2022 08:31:10 +0300