关于递归问题

Question

**请问下大神们，代码是如何的执行顺序的？其中当 test(n-1) == 1 return n
出来后，test(n-1)*n这里是如何运算执行的？

function test(n){
    if ( n == 1 ){
        return n;
    }
    return test(n-1)*n 
}; 
alert( test(4) );

Answer 1

1.递归算法：需要确定递归基，递归体;
2.递归基：就是问题的最简单的形式；

if ( n == 1){
    return n
}

3.递归体：确定递归体就需要确定递归层之间的关系。

retrun test(n-1)*n;

4.递归层之间的关系：上一层只需确定和下一层的关系，每一个递归层的关系必须可以确定。
5.举例：test(4):

// test(4) --> test(3)*4
// test(3) --> test(2)*3
// test(2) --> test(1)*2
// test(1) --> 1
// 递归运算：test(4) = ((test(1)*2)*3)*4 (此处‘=’理解为赋值操作符) 

6.总结：递归就是一种给出自己的最简单的运算形式，和能确定自己两两相邻的层之间的运算关系的，自己高层调用自己低层的运算方式。

Answer 2

test(4)=4*test(3)
test(3)=3*test(2)
test(2)=2*test(1)
test(1)=1

相当于把函数展开替换下

用递归思想解释就是
test(n) //计算n！
由于n! = (n-1)!*n
所以 test(n) 应该return test(n-1)*n
边界值为n==1时，也即1!
其值为1（或者说n）

Answer 3

这不就是计算n的阶乘么。
4（4-1）>>> 43＊（3-1）>>> 432＊（2-1）>>> 432*1

Answer 4

你没有说清楚自己想问什么。

所谓递归，个人的理解是将复杂问题缩小规模，直到形成一个已知的值。层层调用，层层返回。像你贴出的程序，n逐次减小，直到为1，这个时候得到确定的值，然后再逐次返回，最终得到结果。

Answer 5

递归其实非常简单。
我来教题主一个分析递归的好方法。

先说一下递归为什么简单：首先把递归放到一边，考虑一个函数a调用另一个函数b的情况：

function a(m){
    return b(m * 10);
}

function b(n){
    return n + 5;
}

console. log(a(3));

简单吗？非常简单。

接下来，考虑递归。递归其实是一个函数调用另一个函数的特殊情况，特殊在哪里？特殊在调用和被调用的是同一个函数。

既然非特殊情况(a调用b)很简单，那么你把特殊情况转换成非特殊情况(test调用test)来考虑不就变简单了吗？

所以分析递归的方法很简单：将递归变成等价的非递归。

以你的代码为例，你不要把它当成test调用test，而是当成test1调用test2，test2又调用test3...

只不过，这些test1、test2、test3...函数的函数体是相同的。

所以，现在，你的代码就转换成了：

function test1(n){ 
    if (n == 1){
        return n; 
    }
    return test2(n-1) * n
}; 

function test2(n){ 
    if (n == 1){
        return n; 
    }
    return test3(n-1) * n
}; 

function test3(n){ 
    if (n == 1){
        return n; 
    }
    return test4(n-1) * n
}; 

function test4(n){ 
    if (n == 1){
        return n; 
    }
    return test5(n-1) * n
};

...
...
...
// 根据需要可以无限地写下去

alert(test1(4));

你在问题中问的，实际就是test3调用test4的情况。

现在是不是觉得很简单了？！

你可能觉得这种方法很“蠢”，但是对于初学递归的人来说，对于其了解递归的原理非常有效。等你彻底明白了递归的原来后，这种分析方法自然就不需要了。

Answer 6

递归调用顺序的两个过程