經典演演算法-遞迴(生兔子案例)

2020-10-25 07:00:38

前言

演演算法是一個程式設計師必備的知識,從現在開始,來和我學習演演算法吧!

一、什麼是遞迴

遞迴是數學上遞推概念在計算機程式設計上的實現方式,簡單的來說就是一種程式呼叫自身的程式設計技巧。

一個過程或函數在其定義或說明中有直接或間接呼叫自身的一種方法,它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解,遞迴策略只需少量的程式就可描述出解題過程所需要的多次重複計算,大大地減少了程式的程式碼量

二、使用案例

有一對兔子,從出生後第 3 個月起每個月都生一對兔子,小兔子長到第三個月後每個月又生一對兔子,假如兔子都不死,問每個月的兔子總數為多少?

首先對於題進行分析:

前幾個月兔子的數量為:1,1,2,3,5,8,13,21,34,55,89,144,從資料中可以發現從第三個月開始,每個月的兔子數量都是前兩個月兔子數量之和

這個時候就滿足一個遞推的條件,我們就可以在程式中使用遞回來實現這樣一個計算:

int GetNub(int n)   
{
    int nub;
    if(n==1||n==2) nub=2;   
    else nub = GetNub(n-1)+GetNub(n-2);   //在程式中呼叫自身把問題簡化
    return nub;
}

三,如何培養遞迴思想

遞迴思想往往會伴隨時間線的發展而進行,並且前後往往有一定的聯絡,如果遇到這樣的情況,可以考慮列舉出前面的資料,並進行一定的規律總結