Day14:[解题技巧]Recursive - 递回

简单来说就是函式自己呼叫自己的状况，递回由两部分组成

• Recursive Case(递回情况) - 当函式呼叫自己本身的情况
• Base Case(基本状况) - 是当函式不再呼叫自己的条件，也就是终止的条件

递回提供了较为简洁的写法，不过一定要记得设定好终止的条件，避免进入无限循环，把记忆体吃光光。

阶乘 Factorial

在学习递回的时候，大部分的人都会从阶乘开始练习，因为大家高中数学都有学过阶乘，来复习一下甚麽是阶乘 ? 从1连续相乘到n为止，也就是n! = n*(n-1)* …21。

ex.5!=5*4*3*2*1

用js实作阶乘

const factorial = (n) => {
    if (n === 1) return 1;
    return n * factorial(n - 1);
};

factorial(5);

递回在呼叫完自己後会先在原地等待，等待下一层将结果回传，执行顺序如下:

1. factorial(5)会等待 factorial(4)回传结果
2. factorial(4)会等待 factorial(3)回传结果
3. factorial(3)会等待 factorial(2)回传结果
4. factorial(2)会等待 factorial(1)回传结果

当n = 1的时候满足终止递回的条件并回传1

1. factorial(1)回传1
2. factorial(2)回传2*1 =2
3. factorial(3)回传3*2=6
4. factorial(4)回传4*6=24
5. factorial(5)回传5*24 = 120

递回的执行过程可以参考下图，红色箭头是呼叫函式，绿色箭头是回传结果

图片来源:https://www.edureka.co/blog/recursion-in-python/

九九乘法表

以经典的九九乘法表为例，一般我们会直觉地用双回圈来写，其实用递回也可以写出九九乘法表。

//一般写法
const print99 = () => {
    for (let i = 1; i <= 9; i++) {
        for (let j = 1; j <= 9; j++) {
            console.log(`${i}*${j}=${i * j}`);
        }
    }
};

print99();

//用递回(在前端群组看到hello大分享的写法)
const print99ByRecursive = (i, j) => {
    console.log(`${i}*${j}=${i * j}`);
    if (j < 9) return print99(i, j + 1);
    if (i < 9) return print99(i + 1, 1);
};

print99ByRecursive(1, 1);

斐波那契数列

图片来源:https://www.mathsisfun.com/numbers/fibonacci-sequence.html

经典的fibonacci sequence斐波那契数列就很适合用递回来解

甚麽是斐波那契数列?

斐波那契数列由0和1开始，之後的斐波那契数列就是由前两位数字相加而得出 ，也就是第n项为第n-1和第n-2项的总和  - 引用自wikipedia

图片来源:https://www.mathsisfun.com/numbers/fibonacci-sequence.htmlex.

ex.若要取得数列中的第11个数字的话公式为: 89 = 55+34 (n11 = n10 + n9)

用js实作斐波那契数列

const fibonacci = (i) => {
    if (i === 0 || i === 1) return i;
    return fibonacci(i - 1) + fibonacci(i - 2);
};

fibonacci(5);

单看程序码应该会觉得很抽象，所以可以搭配下面这张图来看，由於斐波那契数列的规则是每个数字都是前面两个数相加的总和，画成图的话会发现结构很像binary tree。

图片来源:https://gopigorantala.com/fibonacci-number-java-ways-to-optimise-2/

不过眼尖的你可能会发现一个问题，有些函式明明已经有执行过，却还是重复执行，像是fib(2) 、fib(1)，因为递回的本质是将问题拆解成多个小问题，而这些小问题可能会有重叠的状况，因此并不会记得那些部分是已经运算过的，所以就会发生重复运算的问题，执行效率较差，这就是递回其中一个缺点。

除此之外，还可能发生stack overflow(堆叠溢位 - stack满出来)的问题，在讨论stack overflow之前，先来复习一下执行堆叠（call stack）的观念

图片来源:https://mlog.club/article/5741653

由於JavaScript是单执行绪的语言，一次只能做一件事情，所以使用具有後进先出特性的stack来储存函式的执行环境，每次有新的任务加入的时候，就会像叠盘子一样，一层一层往上叠加，JavaScript会先处理最顶端的函式，当函式执行完并且return之後，该函式就会被移除，接下来处理下一个函式，直到stack被清空为止。

因为递回会不断的呼叫自己的特性，就会一直把函式添加到stack里面，如果递回太深层的话就会发生stack overflow。

图片引用:https://www.tutorialspoint.com/data_structures_algorithms/recursion_basics.htm

除了上述的问题，递回在呼叫函式的时候，为了保存当下执行的状况，会将用到的区域变数、参数、返回位址暂存起来，因此会占用比较多的记忆体空间。

尾递回(tail recursion)

以往的作法会将运算结果储存成区域变数，尾递回则是改将运算结果当成参数传给下层的函式，这个情况称为尾递回。

假设现在有个函式的功能是累加数字，用一般的递回写法如下:

const recsum = (x) => {
    if (x === 1) {
        return x;
    } else {
        return x + recsum(x - 1);
    }
}

假如执行函式recsum(5)，则javaScript的执行顺序如下，函式需要等待下一个函式，直到中止条件後才开始回传结果，然後将值一个一个加总起来

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15

改成尾递回的话，变成使用传入参数的方式来记录当下累积的数字是多少

const tailrecsum = (x, running_total = 0) => {
    if (x === 0) {
        return running_total;
    } else {
        return tailrecsum(x - 1, running_total + x);
    }
}

执行的顺序如下，可以发现初次呼叫的时候就开始计算累加值，不需要用额外的变数去纪录，减少stack的用量

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

在查递回资料的时候一直看到这句话

递回只应天上有，凡人应当用回圈

的确一开始接触递回的时候，觉得有点超出大脑的负荷，因为递回不像回圈那麽直观好懂，直到看了大量的图文解说，才比较理解递回的运作机制，其实递回能做的事，回圈也可以做到，而且递回的执行时间还比较长甚至还比较占用记忆体空间呢!但是递回的写法通常会比回圈来的更简洁，可读性更好，因此还是看使用的情境来评估要用递回或是回圈来处理问题。

参考资料: 尾呼叫
what-is-tail-recursion