递归面试题整理以及时间复杂度分析详解编程语言

   递归具有很多的优点，它可以将一个大的问题划分为小的子问题，然后再逐步细分，达到解决问题的目的。递归的实现借用了栈桢的建立和销毁，所以它是很方便的。但是递归也有一些缺点，比如说，如果递归调用太深，栈桢消耗过大，就会出现栈溢出的问题，因此，在我们使用递归之前，应该仔细考虑适不适合使用递归来解决这个问题。同时，递归深度太深，也会使得运算时间大大增加，所以递归的结论一般都是在理论的基础上的。这篇文章整理了我最近做过的关于递归的一些经典问题，希望对你们会有所帮助。

  这是要讲的六个面试题

     1.递归法求斐波那契数列

     2.递归计算n的k次方

     3.递归计算一个数字每一位相加的结果

     4.递归逆序输出字符串

     5.递归求字符串长度

     6.递归求阶乘

一.递归法求斐波那契数列

         在这里我先要说的是，递归法求菲波那切数列并不是一个很好的解决办法，如果你要问我为什么，其实前面也提到了，如果求第10个或者第20数的值，还好，但是如果要求第100个呢？这样做消耗的栈桢将会是很大的，我先拿一张图来大概表示一下栈桢的消耗过程

并且，随着递归次数越多，时间复杂度也会越高，综合这两点，我觉得用循环来代替递归是很明智的选择。当然我也不是就说递归不好了，有时候用递归解决问题还是相当给力的。菲波那切数列求值，思想就是每一个值都是前面两个数的和，因此放到递归里面就可以分解为子问题，求前两个数字的结果，就这样一直往前走，直到遇到1就返回，然后再把值一个个相加，得到最后的结果。

代码如下：

#include<stdio.h> 
#include<stdlib.h> 
 
int fabonaci(int i) 
{ 
	if(i<=0) 
		return 0; 
	else if(i==1 ||i==2) 
		return 1; 
	else 
		return(fabonaci(i-1)+fabonaci(i-2)); 
} 
int main() 
{ 
	int ret=0; 
	int i=-2; 
	ret=fabonaci(i); 
    printf("fabponaci number i is %d/n",ret); 
 
 
	system("pause"); 
	return 0; 
}

#include<stdio.h> 
#include<stdlib.h> 
 
int sqrt(int n,int k) 
{ 
	if(k==0) 
       return 1; 
	else 
		return n*sqrt(n ,k-1); 
} 
int main() 
{ 
	int ret=0; 
	int n=2; 
	int k=3; 
	ret=sqrt(n,k); 
    printf("%d ^ %d=%d",n,k,ret); 
	system("pause"); 
	return 0; 
}

#include<stdio.h> #include<stdlib.h>  int DigitSum(int i) { 	 	if(i==0) 		return 0 ; 	else 	{ 		if((i/10)>0) 		{ 		printf("%d+",i%10); 		} 		else         printf("%d",i%10); 		return (i%10+DigitSum(i/10)); 	} 	    }		 int main() { 	int ret=0; 	int i=1729; 	ret=DigitSum(i); 	printf("=%d",ret); 	system("pause"); 	return 0; }

#include<stdio.h> #include<stdlib.h>  void reverse_string(char*s) { 	if(*s =='/0') 	{ 		s--; 		return ; 	} 	reverse_string(s+1); 	printf("%c ",*s); }      int main() { 	char *s="hello";     reverse_string(s);  	system("pause"); 	return 0; }

五.递归求字符串长度

#include<stdio.h> 
#include<stdlib.h> 
 
int my_strlen(char* s) 
{ 
	if(*s == '/0') 
		return 0; 
	else 
		return (1+my_strlen(s+1));//不要用s++，会栈溢出 
} 
 
int main() 
{ 
	char s[]="sfgdsfggdsfgd"; 
	int ret; 
	ret=my_strlen(s); 
    printf("字符串的长度为：%d/n",ret); 
 
 
	system("pause"); 
	return 0; 
}

#include<stdio.h> 
#include<stdlib.h> 
 
int Factorial(int i) 
{ 
	if(i==0) 
		return 1; 
	else 
		return i*(Factorial(i-1)); 
} 
 
int main() 
{ 
	int ret=0; 
	int i=5; 
	ret=Factorial(i); 
	printf("%d的阶乘为：%d/n",i,ret); 
 
	system("pause");  
	return 0; 
}