快捷導(dǎo)航

C語言中遞歸的實(shí)際應(yīng)用與經(jīng)典問題

更新時(shí)間：2021年09月01日 11:28:59 作者：flyyyya

函數(shù)以及函數(shù)的遞歸調(diào)用是學(xué)習(xí)C語言必須要掌握的內(nèi)容,且遞歸作為經(jīng)典的算法思想被廣泛應(yīng)用于程序設(shè)計(jì)中,下面這篇文章主要給大家介紹了關(guān)于C語言中遞歸的實(shí)際應(yīng)用與經(jīng)典問題的相關(guān)資料,需要的朋友可以參考下

一、什么是遞歸

遞歸簡單的來說就是在函數(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é)問題中常用的方法。

首先我們?cè)O(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è)盤子,
	}
}

青蛙跳臺(tái)階

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

解題思路

我們?cè)O(shè)臺(tái)階數(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層臺(tái)階時(shí)，青蛙可以選擇先跳1層，剩下2層臺(tái)階，所以此時(shí)就是有2層臺(tái)階時(shí)的跳法，有2種；當(dāng)青蛙選擇第一次跳2層臺(tái)階時(shí)，剩下1層臺(tái)階，此時(shí)有1層臺(tái)階時(shí)的跳法，所以3層臺(tái)階時(shí)的方法是：2層臺(tái)階的方法 + 1層臺(tái)階的方法。

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