一、什么是遞回

遞回簡單的來說就是在函式中呼叫自己
它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞回策略只需少量的程式就可描述出解題程序所需要的多次重復計算，大大地減少了程式的代碼量，
遞回的兩個必要條件：
存在限制條件，當滿足這個限制條件的時候，遞回便不再繼續，
每次遞回呼叫之后越來越接近這個限制條件，

二、遞回模板

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

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296580.html

標籤：其他

上一篇：Jmeter--【作為測驗你必須要知道的】基礎名詞與環境搭建

下一篇：【資料結構】佇列的簡單理解和基本操作