递归(9)

安全守望者 lv.1

发布时间：2022-11-18 20:16:01 296

相关标签：

什么是递归

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

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

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

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

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

递归的两个必要条件

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

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

例1：一个最简单的递归

#include 
int main(){
  printf("hello world!\n");
  //递归
  main();
  return 0;
}

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

注：内存区域的简单划分

递归(9)_#include

内存区域的简单划分

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

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

#include 
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;
}

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

考虑临时变量的情况：

法一：借助库函数

#include 
#include 
int main(){
  char arr[]="bit";
  int len=strlen(arr);
  printf("%d\n",len);
  
  return 0;
}

法二：借助子函数

#include 
#include 
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;
}

不考虑临时变量的情况：

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

#include 
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;
}

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

例3:求n的阶乘n！

循环方式：

#include 
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;
}

递归方式：

#include 
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 1 2 3 5 8 13 21 ...

法一：递归法

#include 
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;
}

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

法二：其他

#include 
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;
}

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

文章来源： https://blog.51cto.com/u_15714963/5549553

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。