C語言中遞歸的示例分析

小編給大家分享一下C語言中遞歸的示例分析，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

一、什么是遞歸

遞歸簡單的來說就是在函數中調用自己

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

遞歸的兩個必要條件：

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

每次遞歸調用之后越來越接近這個限制條件。

二、遞歸模板

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

三、遞歸的實際應用

1.階乘遞歸

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

2.斐波那契數列

斐波那契數列指的是這個數列從第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;
}

四、遞歸的經典問題

漢諾塔問題

漢諾塔問題來源：

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

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

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

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

再來看多個盤

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 級臺階有多少種跳法?

解題思路

我們設臺階數位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;
}

以上是“C語言中遞歸的示例分析”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！