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

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

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

一、什么是遞歸

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

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

遞歸的兩個必要條件：

存在限制條件，當滿足這個限制條件的時候，遞歸便不再繼續(xù)。

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

二、遞歸模板

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

三、遞歸的實際應用

1.階乘遞歸

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

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

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

遞歸算法：

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)塔）問題是源于印度一個古老傳說的益智玩具。大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

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

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

其次我們看兩個盤，三根柱子兩個盤，先將上面的柱子移動到中間柱，然后將最下面的柱子移動到目標柱，最后中間的柱子。

再來看多個盤

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);//遞歸處理,一開始的時候,先將n-1個盤子移至過渡柱z上后再將最底下的大盤子直接移至目標柱子y
		printf("%c->&c\n", a, c);
		hanno(n - 1, b, a, c);//然后重復以上步驟,遞歸處理放在過渡柱z上的n-1個盤子,
	}
}

青蛙跳臺階

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

解題思路

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

當N=1時，當然只有1種跳法；

當N=2時，青蛙可以跳2次1層和跳1次2層；

當N=3時，當有3層臺階時，青蛙可以選擇先跳1層，剩下2層臺階，所以此時就是有2層臺階時的跳法，有2種；當青蛙選擇第一次跳2層臺階時，剩下1層臺階，此時有1層臺階時的跳法，所以3層臺階時的方法是：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;
}