尾递归

add' -> + mul add' | ε

对于这条规则里的递归，有个术语叫尾递归。即产生式箭头的右边在尾部调用产生式的箭头左边。尾递归改写为循环是优化写法。因为循环比递归在系统开销上更少。

计算n的阶乘，n*(n-1)*(n-2)*...*1

记f(n)表示n的阶乘，则f(n) = n * f(n-1)

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

这个就是典型的尾递归。改写成循环

int factorial(int n) {
    int result = 1;
    while(n > 1) {
        result *= n;
        n--;
    }
    return result;
}