递归思想

  数据结构第五章讲述的递归，算法较复杂时，递归对时间和空间的要求很大，但是递归的一个好处就是可以大大简化代码，便于阅读。有回溯的递归转化为非递归时非常麻烦，称为复杂的递归

question1:通过在主函数里调用自定义函数print（5）；在屏幕上输出

1

2 2

3 3 3

4 4 4 4

5 5 5 5 5

  void print（int n）

{

int i;

if(n！=0)//出口

{

print(n-1);

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

printf(" %d",i);

printf("\n");

}

}

一些人可能会以为输出的是

5 5 5 5 5

4 4 4 4

3 3 3

2 2

1

这是不正确的，真正的执行过程如下：

回溯print（5）

{

print（4）；/*执行到print（4）会继续递归下去，不会执行下面的语句*/

for(i=1;i<=5;I++)

printf(" %d",i);

printf("\n");

}

 

print（4）

{

print（3）；

for(i=1;i<=4;I++)

printf(" %d",i);

printf("\n");

}

print（3）

{

print（2）；

for(i=1;i<=3;I++)

printf(" %d",i);

printf("\n");

}

print（3）

{

print（2）；

for(i=1;i<=3;I++)

printf(" %d",i);

printf("\n");

}

print（2）

{

print（1）；

for(i=1;i<=1;I++)

printf(" %d",i);

printf("\n");

}

调用print（1）；/*由于print（0）不满足if语句， 所以print（1）为print（5）的真正起点，开始递归*/