一、什么是遞歸

遞歸簡單的來說就是在函數(shù)中調(diào)用自己

它通常把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。

遞歸的兩個(gè)必要條件：

存在限制條件，當(dāng)滿足這個(gè)限制條件的時(shí)候，遞歸便不再繼續(xù)。

每次遞歸調(diào)用之后越來越接近這個(gè)限制條件。

二、遞歸模板

void recursion(參數(shù)0) 
{
    if (終止條件)
    {
        return;
    }
    else
    {
        recursion(參數(shù)1)
    }
}

三、遞歸的實(shí)際應(yīng)用

1.階乘遞歸

int tmp(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else
	{
		return n*tmp(n - 1);
	}
}

2.斐波那契數(shù)列

斐波那契數(shù)列指的是這個(gè)數(shù)列從第3項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和。

遞歸算法：

int fibonacci(int n)
{
	if (n<=2)
		return 1;
	else
	{
		return fibonacci(n - 1) + fibonacci(n - 2);
	}
}

非遞歸方法：

int fibonacci(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}

四、遞歸的經(jīng)典問題

漢諾塔問題

漢諾塔問題來源：

漢諾塔（又稱河內(nèi)塔）問題是源于印度一個(gè)古老傳說的益智玩具。大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤。

這里我們使用的方法是從特殊到一般，這也是數(shù)學(xué)問題中常用的方法。

首先我們設(shè)計(jì)一個(gè)盤，那就直接把這個(gè)盤從自身柱子移到目標(biāo)柱。

其次我們看兩個(gè)盤，三根柱子兩個(gè)盤，先將上面的柱子移動(dòng)到中間柱，然后將最下面的柱子移動(dòng)到目標(biāo)柱，最后中間的柱子。

再來看多個(gè)盤

void hanno(int n, char a, char b, char c)
{
	if (n == 1)
	{
		printf("%c->%c\n", a, c);
	}
	else
	{
		hanno(n - 1, a, c, b);//遞歸處理,一開始的時(shí)候,先將n-1個(gè)盤子移至過渡柱z上后再將最底下的大盤子直接移至目標(biāo)柱子y
		printf("%c->&c\n", a, c);
		hanno(n - 1, b, a, c);//然后重復(fù)以上步驟,遞歸處理放在過渡柱z上的n-1個(gè)盤子,
	}
}

青蛙跳臺階

一只青蛙可以一次跳 1 級臺階或一次跳 2 級臺階,例如:跳上第一級臺階只有一種跳法:直接跳 1 級即可。跳上兩級臺階,有兩種跳法: 每次跳 1 級,跳兩次; 或者一次跳 2 級.問要跳上第 n 級臺階有多少種跳法?

解題思路

我們設(shè)臺階數(shù)位N;

當(dāng)N=1時(shí)，當(dāng)然只有1種跳法；

當(dāng)N=2時(shí)，青蛙可以跳2次1層和跳1次2層；

當(dāng)N=3時(shí)，當(dāng)有3層臺階時(shí)，青蛙可以選擇先跳1層，剩下2層臺階，所以此時(shí)就是有2層臺階時(shí)的跳法，有2種；當(dāng)青蛙選擇第一次跳2層臺階時(shí)，剩下1層臺階，此時(shí)有1層臺階時(shí)的跳法，所以3層臺階時(shí)的方法是：2層臺階的方法 + 1層臺階的方法。

#include<stdio.h>
int frog(int n)
{
   if(n == 1)
   {
      return 1;
   }
   if(n == 2)
   {
      return 2;
   }
   return frog(n-1) + frog(n-2);
}
int main()
{
   int n;
   scanf("%d",&n);
   int ways = frog(n);
   printf("%d\n",ways);
   return 0;
}

總結(jié)

到此這篇關(guān)于C語言中遞歸的實(shí)際應(yīng)用與經(jīng)典問題的文章就介紹到這了,更多相關(guān)C語言中遞歸應(yīng)用內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論