一.遞歸法求斐波那契數列

在這里我先要說的是，遞歸法求菲波那切數列并不是一個很好的解決辦法，如果你要問我為什么，其實前面也提到了，如果求第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;
}

二.遞歸計算n的k次方

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

代碼如下

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

三.遞歸計算一個數字每一位相加的結果

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

代碼如下

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

五.遞歸求字符串長度

一個字符串的長度等于每一個字符相加的結果，因此可以轉化為子問題，要求整個的長度，就是要求少一位的字符串的長度加一，這樣逐級建立棧楨，到達結束條件 \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;
}

以上就是“遞歸面試題的一些常見問題整理”，你能回答上來嗎?如果想要了解更多的Java面試題相關內容，可以關注動力節點Java官網。