關鍵區別——遞歸與迭代
遞歸和迭代可以用來解決編程問題。使用遞歸或迭代來解決問題的方法取決於解決問題的方式。遞歸和迭代的關鍵區別在於遞歸是一種在同一個函數中調用函數的機制,而迭代是重複執行一組指令,直到給定的條件為真。遞歸和迭代是開發算法和構建軟件應用程序的主要技術。
目錄
1. 概述和主要區別
2. 什麼是遞歸
3. 什麼是迭代
4. 遞歸與迭代的相似性
5. 並排比較-遞歸與表格形式的迭代
6. 摘要
什麼是遞歸(recursion)?
當函數在函數內調用自身時,稱為遞歸。遞歸有兩種類型。它們是有限遞歸和無限遞歸。有限遞歸有一個終止條件。無限遞歸沒有終止條件。
遞歸可以用計算階乘的程序來解釋。
n!=n*(n-1)!,如果n>0
n!n=1時;
參考下面的代碼計算3(3)的階乘!=3*2*1)。
intmain公司(){
int值=階乘(3);
printf(“Factorial is%d\n”,value);
返回0;
}
內因子(intn){
如果(n==0){
返回1;
}
其他{
返回n*階乘(n-1);
}
}
當調用factorial(3)時,該函數將調用factorial(2)。當調用factorial(2)時,該函數將調用factorial(1)。那麼factorial(1)將調用factorial(0)。階乘(0)將返回1。在上述程序中,“if塊”中的n==0條件是基本條件。同樣,階乘函數被反覆調用。
遞歸函數與堆棧相關。在C語言中,主程序可以有許多功能。所以,main()是調用函數,main程序調用的函數就是被調用函數。當函數被調用時,控制權被賦予被調用的函數。函數執行完成後,控件返回main。然後主程序繼續。因此,它會創建一個激活記錄或堆棧幀來繼續執行。
在上面的程序中,當從main調用factorial(3)時,它在調用堆棧中創建一個激活記錄。然後,在堆棧頂部創建factorial(2)堆棧幀,依此類推。激活記錄保存有關局部變量等的信息。每次調用函數時,都會在堆棧頂部創建一組新的局部變量。這些堆棧幀可以減慢速度。同樣,在遞歸中,函數調用自身。遞歸函數的時間複雜度是由函數被調用的次數發現的。一個函數調用的時間複雜度為O(1)。對於n個遞歸調用,時間複雜度為O(n)。
什麼是迭代(iteration)?
迭代是一個指令塊,它一次又一次地重複,直到給定的條件為真。迭代可以用“for循環”、“do while循環”或“while循環”來實現。“for loop”語法如下。
for(初始化;條件;修改){
//聲明;
}
初始化步驟首先執行。這一步是聲明和初始化循環控制變量。如果條件為true,則執行大括號內的語句。這些語句執行到條件為true為止。如果條件為false,則控件將轉到“for循環”之後的下一個語句。在循環中執行語句之後,控件轉到modify部分。它是更新循環控制變量。然後再次檢查條件。如果條件為true,則將執行大括號內的語句。這樣,“for循環”迭代。
在“while循環”中,循環內的語句將一直執行,直到條件為真。
while(條件){
//陳述
}
在“do while”循環中,在循環結束時檢查條件。因此,循環至少執行一次。
做{
//陳述
}while(條件)
3的階乘3使用迭代(“for loop”)如下所示。
內部主(){
intn=3,階乘=1;
英蒂;
對於(i=1;i<=n;i++){
階乘=階乘*i;
}
“階乘(printis\Factorial)”(printis-d,Factorial%n);
返回0;
}
遞歸(recursion)和迭代(iteration)的共同點
- 兩者都是解決問題的技巧。
- 這個任務可以用遞歸或迭代的方式來解決。
遞歸(recursion)和迭代(iteration)的區別
遞歸與迭代 | |
遞歸是在同一個函數內調用函數的一種方法。 | 迭代是在給定條件為真之前重複的一組指令。 |
空間複雜性 | |
遞歸程序的空間複雜度高於迭代。 | 迭代的空間複雜度較低。 |
速度 | |
遞歸執行緩慢。 | 通常,迭代比遞歸快。 |
條件 | |
如果沒有終止條件,則可能存在無限遞歸。 | 如果條件永遠不會變為false,那麼它將是一個無限的迭代。 |
堆棧 | |
在遞歸中,調用函數時,堆棧用於存儲局部變量。 | 在迭代中,不使用堆棧。 |
代碼可讀性 | |
遞歸程序更具可讀性。 | 迭代程序比遞歸程序更難閱讀。 |
總結 - 遞歸(recursion) vs. 迭代(iteration)
本文討論了遞歸與迭代的區別。兩者都可以用來解決編程問題。遞歸和迭代的區別在於,遞歸是一種機制,在同一個函數中調用一個函數,然後迭代它,反覆執行一組指令,直到給定的條件為真。如果一個問題可以用遞歸的形式來解決,那麼它也可以通過迭代來解決。
下載遞歸vs迭代的pdf版本
你可以下載這篇文章的PDF版本,並按照引文說明離線使用。請在這裡下載PDF版本遞歸和迭代的區別
引用
1.要點,教程。“數據結構和算法遞歸基礎”,教程點,2017年8月15日。此處提供2.nareshtechnologies。“C函數遞歸| C語言教程”,YouTube,YouTube,2016年9月12日。這裡有3.yusuf Shakel。“遞歸算法|階乘-分步指南”,YouTube,YouTube,2013年10月14日。此處提供
2.nareshtechnologies公司。“C函數遞歸| C語言教程”,YouTube,YouTube,2016年9月12日。
3.優素福·沙克爾。“遞歸算法|階乘-分步指南”,YouTube,YouTube,2013年10月14日。