递归函数

先举个比较简单的例子——当k=3时：

（给你的程序加上行号，以便解释）

/程序段1（k=3）/

Line1: p(3)

Line2: {

Line3: if (3>0)

Line4: { std::cout<<3<<" "<<std::endl;

Line5: p(2);

Line6: p(2);

Line7: }

Line8: }

程序段1执行到第4行时，屏幕上显示“3 ”（注：引号不包括在内，下同）

接着执行到第5行，进入函数p(2):

/程序段2（k=2）/

Line1: p(2)

Line2: {

Line3: if (2>0)

Line4: { std::cout<<2<<" "<<std::endl;

Line5: p(1);

Line6: p(1);

Line7: }

Line8: }

程序段2执行到第4行，新输出“2 ”，屏幕上显示“3 2 ”；

执行到第5行，进入函数p(1)：

/程序段3（k=1）/

Line1: p(1)

Line2: {

Line3: if (1>0)

Line4: { std::cout<<1<<" "<<std::endl;

Line5: p(0);

Line6: p(0);

Line7: }

Line8: }

程序段3执行到第4行，新输出“1 ”，屏幕上显示“3 2 1 ”；

执行到第5行，进入函数p(0)：

/程序段4（k=0）/

Line1: p(0)

Line2: {

Line3: if (0>0)

Line4: { std::cout<<0<<" "<<std::endl;

Line5: p(-1);

Line6: p(-1);

Line7: }

Line8: }

程序段4执行到第3行，判断条件为假，不再往下执行，程序段3第5行的函数p(0)结束，程序段3继续执行第6行，又是函数p(0)，同理，不输出任何东西，结束。

然后程序段3执行完毕，即程序段2第5行的函数p(1)结束，程序段2继续执行第6行，又进入函数p(1)，输出“1 ”，屏幕上显示“3 2 1 1 ”……如此往复，直至p(3)执行完毕，即程序段1执行完毕。

最后结果为屏幕上显示：

3 2 1 1 2 1 1

同理，我们可以知道k=4的输出情况：

4 3 2 1 1 2 1 1 3 2 1 1 2 1 1

以及k=5的情况：

5 4 3 2 1 1 2 1 1 3 2 1 1 2 1 1 4 3 2 1 1 2 1 1 3 2 1 1 2 1 1

简单地说，递归就是函数方法自我调用，使复杂问题一步一步朝目标简化。

如： 典型的问题， 求n的阶乘

int product(int n)

{

if (n==1) return 1

else return n product(n-1) // 用 n product (n-1)

}

非递归算法：

int product(int n)

{

int result = 1;

for (int i=1; i<=n; i++)

{ result=result i }

}