一.遞歸法求斐波那契數(shù)列

在這里我先要說的是，遞歸法求菲波那切數(shù)列并不是一個(gè)很好的解決辦法，如果你要問我為什么，其實(shí)前面也提到了，如果求第10個(gè)或者第20數(shù)的值，還好，但是如果要求第100個(gè)呢?這樣做消耗的棧楨將會是很大的，我先拿一張圖來大概表示一下棧楨的消耗過程

并且，隨著遞歸次數(shù)越多，時(shí)間復(fù)雜度也會越高，綜合這兩點(diǎn)，我覺得用循環(huán)來代替遞歸是很明智的選擇。當(dāng)然我也不是就說遞歸不好了，有時(shí)候用遞歸解決問題還是相當(dāng)給力的。

菲波那切數(shù)列求值，思想就是每一個(gè)值都是前面兩個(gè)數(shù)的和，因此放到遞歸里面就可以分解為子問題，求前兩個(gè)數(shù)字的結(jié)果，就這樣一直往前走，直到遇到1就返回，然后再把值一個(gè)個(gè)相加，得到最后的結(jié)果。

代碼如下

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

二.遞歸計(jì)算n的k次方

遞歸一般都是逆序思想，要求n的k次方，那就先求n的k-1次方，而要求n的k-1次方，就要求k-2次方，就這樣一直給前走，直到求n的0次方為終止條件。而n的k次方就是k個(gè)n相乘，所以，只需要每次返回時(shí)乘上n就可以得到最終的結(jié)果

代碼如下

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

三.遞歸計(jì)算一個(gè)數(shù)字每一位相加的結(jié)果

要想得到一個(gè)數(shù)字的每一位，最簡單的辦法就是%10 /10，如此反復(fù)幾次，直到i==0為止，而要讓每一位都相加，那就在 return 后面返回一個(gè)范圍縮小的值 加上%10的值，當(dāng)函數(shù)得到第一位數(shù)字時(shí)就開始返回結(jié)果，這個(gè)遞歸問題是線性的，所以棧楨消耗并不會很大

代碼如下

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

四.遞歸逆序輸出字符串

這個(gè)問題其實(shí)用遞歸也是很好解決的，原因就在于，遞歸的創(chuàng)建是逆思路進(jìn)行的，它會把你要得到的結(jié)果在函數(shù)到達(dá)終止條件時(shí)開始返回，因此，你只需要定義一個(gè)指針，讓它一直走到字符串的結(jié)束位置，然后開始打印字符串，這樣屏幕上輸出的字符串就一定是逆序的

代碼如下

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

五.遞歸求字符串長度

一個(gè)字符串的長度等于每一個(gè)字符相加的結(jié)果，因此可以轉(zhuǎn)化為子問題，要求整個(gè)的長度，就是要求少一位的字符串的長度加一，這樣逐級建立棧楨，到達(dá)結(jié)束條件 \0 時(shí)就可以得到最終的結(jié)果

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

以上就是“遞歸面試題的一些常見問題整理”，你能回答上來嗎?如果想要了解更多的Java面試題相關(guān)內(nèi)容，可以關(guān)注動力節(jié)點(diǎn)Java官網(wǎng)。