当前位置：网站首页>C语言基础演练(9)

C语言基础演练(9)

2022-08-05 21:55:00 【51CTO】

什么是递归

程序调用自身的编程技巧称为递归(recursion)。

递归作为一种算法在程序设计语言中广泛应用。

一个过程（或函数）在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解；

递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的主要思考方式在于:把大事化小

递归的两个必要条件

1.存在限制条件：当满足该限制条件时，递归就结束；

2.每次递归调用之后越来越接近该限制条件。

例1：一个最简单的递归

       
       #include <stdio.h>
       
       int 
       
       main(){
       
       printf(
       
       "hello world!\n");
       
       //递归
       
       main();
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.

这种最简单的递归存在的问题：栈溢出问题---stackoverflow

注：内存区域的简单划分

C语言基础演练(9)_递归

内存区域的简单划分

例2：接受一个整型值（无符号），按照顺序打印它的每一位。

例如：1234，输出1 2 3 4.

       
       #include <stdio.h>
       
       void 
       
       print(
       
       int 
       
       n){
       
       if(
       
       n
       
       >
       
       9){
       
       print(
       
       n
       
       /
       
       10);
       
  }
       
       printf(
       
       "%d",
       
       n
       
       %
       
       10);
       
}
       
       int 
       
       main(){
       
       unsigned 
       
       int 
       
       num
       
       =
       
       0;
       
       scanf(
       
       "%d",
       
       &
       
       num);
       
       //递归
       
       print(
       
       num);
       
       //print(1234)
       
       //print(123) 4
       
       //print(12) 3 4
       
       //print(1) 2 3 4
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.

例3：编写函数不允许创建临时变量，求字符串的长度

考虑临时变量的情况：

法一：借助库函数

       
       #include <stdio.h>
       
       #include <string.h>
       
       int 
       
       main(){
       
       char 
       
       arr[]
       
       =
       
       "bit";
       
       int 
       
       len
       
       =
       
       strlen(
       
       arr);
       
       printf(
       
       "%d\n",
       
       len);
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.

法二：借助子函数

       
       #include <stdio.h>
       
       #include <string.h>
       
       int 
       
       my_strlen(
       
       char
       
       * 
       
       str){
       
       int 
       
       count
       
       =
       
       0;
       
       while(
       
       *
       
       str 
       
       != 
       
       '\0'){
       
       count
       
       ++;
       
       str
       
       ++;
       
  }
       
       return 
       
       count;
       
}
       
       int 
       
       main(){
       
       char 
       
       arr[]
       
       =
       
       "bit";
       
       int 
       
       len
       
       =
       
       my_strlen(
       
       arr);
       
       //arr是数组;
       
       //数组传参，传过去的不是整个数组，而是第一个元素的地址
       
       printf(
       
       "%d\n",
       
       len);
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.

不考虑临时变量的情况：

法~：借助递归----大事化小

       
       #include <stdio.h>
       
       int 
       
       my_strlen(
       
       char
       
       * 
       
       str){
       
       if(
       
       *
       
       str 
       
       != 
       
       '\0'){ 
       
       //第一个元素不是'\0'的情况
       
       return 
       
       1
       
       +
       
       my_strlen(
       
       str
       
       +
       
       1);
       
   }
       
       else{ 
       
       //第一个元素是'\0'的情况
       
       return 
       
       0;
       
  }
       
}
       
       //大事化小
       
       //my_strlen(”bit\0“)
       
       //1+my_strlen(“it\0”)
       
       //1+1+my_strlen(”t\0“)
       
       //1+1+1+my_strlen(”\0“)
       
       //1+1+1+0
       
       //3
       
       int 
       
       main(){
       
       char 
       
       arr[]
       
       =
       
       "bit";
       
       int 
       
       len
       
       =
       
       my_strlen(
       
       arr);
       
       //arr是数组;
       
       //数组传参，传过去的不是整个数组，而是第一个元素的地址
       
       printf(
       
       "%d\n",
       
       len);
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.

循环方式与递归方法的对比

例3:求n的阶乘n！

循环方式：

       
       #include <stdio.h>
       
       int 
       
       Fac1(
       
       int 
       
       n){
       
       int 
       
       i;
       
       int 
       
       ret
       
       =
       
       1;
       
       for(
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       n;
       
       i
       
       ++){
       
       ret
       
       *=
       
       i;
       
  }
       
       return 
       
       ret;
       
}
       
       int 
       
       main(){
       
       int 
       
       n
       
       =
       
       0;
       
       int 
       
       ret
       
       =
       
       0;
       
       scanf(
       
       "%d",
       
       &
       
       n);
       
       ret
       
       =
       
       Fac1(
       
       n);
       
       //循环方式
       
       printf(
       
       "%d\n",
       
       ret);
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.

递归方式：

       
       #include <stdio.h>
       
       int 
       
       Fac2(
       
       int 
       
       n){
       
       if(
       
       n
       
       <
       
       1){
       
       return 
       
       1;
       
  }
       
       else
       
       return 
       
       n
       
       *
       
       Fac2(
       
       n
       
       -
       
       1);
       
}
       
       int 
       
       main(){
       
       int 
       
       n
       
       =
       
       0;
       
       int 
       
       ret
       
       =
       
       0;
       
       scanf(
       
       "%d",
       
       &
       
       n);
       
       ret
       
       =
       
       Fac2(
       
       n);
       
       //递归方式
       
       printf(
       
       "%d\n",
       
       ret);
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.

注：递归方法可以利用很少的代码就可以实现编程，但其容易出现栈溢出问题，进而影响效率。

裴波纳契数列

1 1 2 3 5 8 13 21 ...

法一：递归法

       
       #include <stdio.h>
       
       int 
       
       Fib(
       
       int 
       
       n){
       
       if(
       
       n
       
       <
       
       2){
       
       return 
       
       1;
       
  }
       
       else
       
       return 
       
       Fib(
       
       n
       
       -
       
       1)
       
       +
       
       Fib(
       
       n
       
       -
       
       2);
       
}
       
       //该方法效率低，速度慢
       
       //50
       
       //49 48
       
       //48 47 47 46
       
       //47 46 46 45 46 45 45 44
       
       //...
       
       int 
       
       main(){
       
       int 
       
       n
       
       =
       
       0;
       
       //第n个裴波纳契数
       
       int 
       
       ret
       
       =
       
       0;
       
       scanf(
       
       "%d",
       
       &
       
       n);
       
       ret
       
       =
       
       Fib(
       
       n);
       
       //递归方式
       
       printf(
       
       "%d\n",
       
       ret);
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.

注：这里使用递归方法效率低，速度慢

法二：其他

       
       #include <stdio.h>
       
       int 
       
       Fib(
       
       int 
       
       n){
       
       int 
       
       a
       
       =
       
       1;
       
       int 
       
       b
       
       =
       
       1;
       
       int 
       
       c
       
       =
       
       1;
       
       while(
       
       n
       
       >
       
       2){
       
       c
       
       =
       
       a
       
       +
       
       b;
       
       a
       
       =
       
       b;
       
       b
       
       =
       
       c;
       
       n
       
       --;
       
  }
       
       return 
       
       c;
       
}
       
       //该方法效率低，速度慢
       
       //50
       
       //49 48
       
       //48 47 47 46
       
       //47 46 46 45 46 45 45 44
       
       //...
       
       int 
       
       main(){
       
       int 
       
       n
       
       =
       
       1;
       
       //第n个裴波纳契数
       
       int 
       
       ret
       
       =
       
       0;
       
       scanf(
       
       "%d",
       
       &
       
       n);
       
       ret
       
       =
       
       Fib(
       
       n);
       
       //递归方式
       
       printf(
       
       "%d\n",
       
       ret);
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.

-------------END------------

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15714963/5549553

当前位置：网站首页>C语言基础演练(9)

C语言基础演练(9)

边栏推荐

猜你喜欢

随机推荐