函数递归（c语言）

递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归只需少量的程序就可以描述出解题过程所需要的多次重复计算，大大减少了程序的代码量。思考方式：通过把大事化小

输入一个整数值，按顺序打印他的每一位，列如：输入12，输出12
代码实现：

#include
void print(int x){
  	if(x>9){	  
	   print(x/10);
	   }
	   printf("%d",x%10);	
	
  }
  int main(){
	int m=0;
	scanf("%d",&m);//输入12 
	print(m);//print函数可以打印参数部分数字的每一位 
	return 0;
} 

实现流程图：

1 存在限制条件,当满足这个限制条件的时候，递归便不再继续
2 每次递归调用之后越来越接近这个限制条件

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

思路：

 int get_strlen(char *arr){
      if(*arr!=''){
   		 return 1+get_strlen(arr+1);//arr+1是下一个字符数组的地址 
	   } else{
	   	return 0;
	   }
   }
  int main(){
	char arr[]="abc";
	printf("%d",get_strlen(arr));
   }

2 求n的阶乘

思路：n*(n-1)(n-2)…*1

 int get_fac(int n)
    {
    	if(n<=1)
    	  return 1;
    	else 
    	  return n*get_fac(n-1);   
	}
   int main(){
	int n=0;
	scanf("%d",&n);
	int ret=get_fac(n);
	printf("%d",ret);
   }

3 求第n个斐波那契数

思路：n>2   (n-1)+(n-2)
      n<=2      1

 int fib(int n){
      if(n<=2)
        return 1;
      else 
    return fib(n-1)+fib(n-2);
	}
    int main(){
	int n=0;
	scanf("%d",&n);
	int ret=fib(n);
	printf("%d",ret); 
} 

通过求第50个斐波那契数可以看出来明显缺陷，使用函数递归效率很低，由于重复使用大量代码，导致特别耗时，所以这个时候用非递归的形式来书写效率就不会很低

1 都要写跳出条件，每次递归逼近跳出条件，不能写死递归
2 递归层次不能太深
3 当用迭代实现比递归效率更高时，使用迭代实现，虽然代码可读性稍微差点
3 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿他所带来的运行时开销