2020-12-10

递归思想

原创思路

我自己也是刚开学 学习了两个月的小白，文章如有错误请各路大佬指出。写这篇文章时我也没有深度思考，可能会有点小瑕疵；

废话我也不多说，直接上代码。

#include <stdio.h>
#include <stdlib.h>
int fun(int i){
 if(i>0){
  fun(i/2);
 }
 printf("%d\n",i);
}
int main(){
 fun(8);
 return 0;
}

上面的代码是老师（我超级崇拜）留的一道作业题，运行的结果想必大家都知道，非常简单。

0
1
2
4
8

但是有没有想过这是怎么运行出来的，先来解释一下吧，当运行fun函数时每当 i>0 时都会执行fun函数，同时也会残留一个printf("%d\n",i)在外部；
我现在用代码实现这个思路：
我首先说明下面的代码运行结果是不对的

#include <stdio.h>
#include <stdlib.h>
int main(){
  int i=8;
  if(i>0){ 
    i=i/2;if(i>0){ 
       i=i/2;if(i>0){ 
          i=i/2;if(i>0){ 
            i=i/2;if(i>0){
                  i=i/2;
               }else printf("%d\n",i);
              }printf("%d\n",i);
          }printf("%d\n",i);
      }printf("%d\n",i);
  } printf("%d\n",i);
 
 return 0;
}

我想传达是一种思想，对于本题每次递归都会残留一个printf在外面，只有执行到你设定的条件时才可以运行下面的程序，也就是递归中的回溯。通过观察我们也可以看到你给的终止条件必须有效，不然它永远不会执行后面的程序，最终也不会给你答案

下面是可以运行正确的答案的代码，但是这段已经脱离我的本意了。

#include <stdio.h>
#include <stdlib.h>
int main(){
  int i=8;
  if(i>0){ 
  printf("%d\n",i);
   i=i/2;if(i>0){ 
   printf("%d\n",i);
    i=i/2;if(i>0){ 
    printf("%d\n",i);
     i=i/2;if(i>0){
     printf("%d\n",i); 
      i=i/2;if(i>0){
       i=i/2;
      }else printf("%d\n",i);
     }
    }
   }
  } 
 
 return 0;
}