數列求和的線性遞迴實現和二分遞迴實現

2022-09-22 18:42:59 字數 837 閱讀 3480

標籤(空格分隔): 資料結構 演算法

以前上c程式設計時,遞迴就搞得糊里糊塗的,甚至連最簡單的一個青蛙跳問題都做不出來。過了幾個月了,因為學習資料結構重新學習了一下,歸納了一下如何寫出一個遞迴程式。

遞迴分為好幾種模式,這裡先介紹線性遞迴和二分遞迴。以對一個整型數列求和為例。先上**。假設最常用的設加和器迴圈累加的方法是樸素法。

//遞迴實現陣列求和

#include

#define n 1005

using

namespace

std;

int s1,s2;

int dichotomysum(int a,int lo,int hi);

int elasticsum(int a,int lo,int hi);

int main()

//此為二分遞迴

int dichotomysum(int a,int lo,int hi)

//此為線性遞迴

int elasticsum(int a,int lo,int hi)

線性遞迴的加和方式仍然像樸素方法一樣,看似沒有迴圈,其實迴圈靠遞迴實現。實現它的操作有:1.平凡條件。就是返回一個平凡值的條件,就像邊界條件一樣。2.一般操作。就是實現累和過程的實際操作。3.相通的引數設定。函式宣告時的形式引數和在函式體內呼叫時的函式引數在邏輯上相通,使函式能通過遞迴呼叫完成累和。

二分遞迴的實現思想略有不同。對每一個大區間折半,然後對每一個小區間求和;對於每一個小區間,繼續該操作,直到區間內只有一個元素,就返回這個元素。顯然,該演算法也包括1.平凡條件。2.一般操作。3.相通的引數設定。這是我認為的遞迴演算法設定中的重點。