1樓:南北
遞迴演算法是一種直接或者間接地呼叫自身的演算法。
在計算機編寫程式中,遞迴演算法對解決一大類問題是十分有效的,它往往使演算法的描述簡潔而且易於理解。
遞迴就是在過程或函式裡呼叫自身。
在使用遞迴策略時,必須有一個明確的遞迴結束條件,稱為遞迴出口。
遞迴演算法解題通常顯得很簡潔,但遞迴演算法解題的執行效率較低。所以一般不提倡用遞迴演算法設計程式。
在遞迴呼叫的過程當中系統為每一層的返回點、區域性量等開闢了棧來儲存。遞迴次數過多容易造成棧溢位。
2樓:匿名使用者
以下是比較全面的解釋,可以看看。 遞迴演算法是一種直接或者間接地呼叫自身的演算法。在計算機編寫程式中,遞迴演算法對解決一大類問題是十分有效的,它往往使演算法的描述簡潔而且易於理解。
遞迴演算法解決問題的特點: (1) 遞迴就是在過程或函式裡呼叫自身。 (2) 在使用遞迴策略時,必須有一個明確的遞迴結束條件,稱為遞迴出口。
(3) 遞迴演算法解題通常顯得很簡潔,但遞迴演算法解題的執行效率較低。所以一般不提倡用遞迴演算法設計程式。 (4) 在遞迴呼叫的過程當中系統為每一層的返回點、區域性量等開闢了棧來儲存。
遞迴次數過多容易造成棧溢位等。所以一般不提倡用遞迴演算法設計程式。
c語言的兩個問題: 所有的遞迴程式均可以用非遞迴演算法實現?遞迴函式中的形式引數是自動變數嗎? c語言中
3樓:匿名使用者
c語言所有遞迴都bai可以用非遞迴演算法實du現,最典型的就是
zhi迭代法dao,有時比遞迴更容專易理解。至
於遞迴中屬的形式引數是自動變數,沒明白樓主的意思,形參就是形參啊,形參變數也是變數,其記憶體分配在棧區,隨著函式的結束,其記憶體也會被釋放,形參的生命週期與函式生命週期相同哈(同生共死)
4樓:匿名使用者
||#include
unsigned int fibonacci(int n);
int main( void )
return 0;
}unsigned int fibonacci(int n)這種演算法效屬率比較低
**不清楚可以hi我
5樓:賊寇在何方
1.是的,藉助堆疊都可以實現
2.是的
程式的遞迴演算法與非遞迴有什麼區別?
6樓:南北
遞迴演算法是一種直接或者間接地呼叫自身的演算法。
在計算機編寫程式中,遞迴演算法對解決一大類問題是十分有效的,它往往使演算法的描述簡潔而且易於理解。
遞迴就是在過程或函式裡呼叫自身。
在使用遞迴策略時,必須有一個明確的遞迴結束條件,稱為遞迴出口。
遞迴演算法解題通常顯得很簡潔,但遞迴演算法解題的執行效率較低。所以一般不提倡用遞迴演算法設計程式。
在遞迴呼叫的過程當中系統為每一層的返回點、區域性量等開闢了棧來儲存。遞迴次數過多容易造成棧溢位。
c語言程式題:寫出遞迴與非遞迴兩種折半查詢程式,並分析其時間空間複雜度。
7樓:匿名使用者
折半查詢需要先對資料進行排序。
#include
using namespace std;
int bsearch(int data, const int x, int beg, int last)
while(beg <= last)
else if (data[mid] < x)
else if (data[mid] > x)
}return -1;
}int rbsearch(int data, const int x, int beg, int last)
else if (x < data[mid])
else if (x > data[mid])
}int main(void)
;//int num = 3;
int num=30;
cout << "the array is : " << endl;
int n = sizeof(data)/sizeof(int);
for (int i = 0; i < n; i++)
cout << endl;
int index = -1;
//index = bsearch(data,num,0,n);
index = rbsearch(data, num, 0,n);
cout << "index of " << num << " is " << index << endl;
system("pause");
return 0;
}以上是氣泡排序演算法的實現。
折半查詢演算法描述如下:
在有序表中,把待查詢資料值與查詢範圍的中間元素值進行比較,會有三種情況出現:
1) 待查詢資料值與中間元素值正好相等,則放回中間元素值的索引。
2) 待查詢資料值比中間元素值小,則以整個查詢範圍的前半部分作為新的查詢範圍,執行1),直到找到相等的值。
3) 待查詢資料值比中間元素值大,則以整個查詢範圍的後半部分作為新的查詢範圍,執行1),直到找到相等的值
4) 如果最後找不到相等的值,則返回錯誤提示資訊。
實現如下:
#include
using namespace std;
int bsearch(int data, const int x, int beg, int last)
while(beg <= last)
else if (data[mid] < x)
else if (data[mid] > x)
}return -1;
}int rbsearch(int data, const int x, int beg, int last)
else if (x < data[mid])
else if (x > data[mid])
return -1;
}int main(void)
;int num = 3;
cout << "the array is : " << endl;
int n = sizeof(data)/sizeof(int);
for (int i = 0; i < n; i++)
cout << endl;
int index = -1;
//inedx=bsearch(data,num,0,n);
index = rbsearch(data, num, 0,n);
cout << "index of " << num << " is " << index << endl;
system("pause");
return 0;
}複雜度分析:
折半查詢就像搜素二叉樹:中間值為二叉樹的根,前半部分為左子樹,後半部分為右子樹。折半查詢法的查詢次數正好為該值所在的層數。
等概率情況下,約為log2(n+1)-1,其演算法複雜度為o(log(n))。
遞迴演算法的是怎麼回事 什麼是遞迴演算法 有什麼作用
和迭代差不多,只是通過定義和呼叫函式來實現迭代把事情分解成相同的步驟重複執行直到符合某一條件時結束,再反過來遞推到最初的狀態,問題就解決了。比如定義 用的是c語言 int fun int a 在fun裡面再定義fun,這個fun都只做一件事,把a的內容和fun a 1 相乘作為返回值。這裡要有個終止...
複製二叉樹的非遞迴演算法 演算法思想和演算法實現
else int pde 0 指向待建立左子樹根和右子樹根的結點dest data sour data de pde dest 先對根結點的複製initqueue q enqueue q,sour while isqempty q 當還沒複製完if p rchild return ok 演算法的思想...
怎樣實現二叉樹的前序遍歷的非遞迴演算法
遞迴不遞迴只是表象,本質都是壓棧,出棧的操作,只不過遞迴是以函式為元素進行的棧操作,不遞迴演算法就是把樹的元素來棧操作,在一個函式內部完成,看起來就沒有遞迴。非遞迴的話,就用堆疊實現了啊 先序遍歷二叉樹的遞迴演算法怎樣理解?二叉樹的結點結構是 1 根結點 存放結點資料 2 左子樹指標 3 右子樹指計...