首頁 Java java教程 Java中的迭代與遞歸實例詳解

Java中的迭代與遞歸實例詳解

Jul 02, 2017 am 10:23 AM
java 實例 遞迴

這篇文章主要為大家介紹了關於Java中的迭代和遞歸文章顯示分別介紹了Java中的迭代和遞歸,而後又介紹了迭代和遞歸的區別以及數形遞歸的相關內容,文中介紹的很詳細,相信會對大家學習具有一定的參考借鑒價值,有需要的朋友們可以參考借鑒。

前言

最近在看書的時候看到這一內容,感覺還蠻有收穫的。迭代使用的是循環(for,while,do...wile)或迭代器,當循環條件不滿足時退出。而遞歸,一般是函數遞歸,可以是自身調用自身,也可以是非直接調用,即方法A調用方法B,而方法B反過來調用方法A,遞歸退出的條件為if,else語句,當條件符合基的時候就退出。

上面是迭代和遞歸的語法特性,他們在Java中有什麼不同呢?下面透過這篇文章來詳細了解了解。

一、遞迴

提到迭代,不得不提一個數學表達式: n! =n*(n-1)*(n-2)*...*1

有很多方法可以計算階乘。有一定數學基礎的人都知道n!=n*(n-1)!因此,程式碼的實作可以直接寫成:

程式碼一

int factorial (int n) {
 if (n == 1) {
  return 1;
 } else {
  return n*factorial(n-1);
 }
}
登入後複製

在執行上述程式碼的時候,其實機器是要執行一系列乘法的: factorial(n) factorial(n-1) factorial(n-2) → … → factorial(1) 。所以,需要不斷的追蹤(追蹤上次計算的結果)並呼叫乘法進行計算(建立一個乘法鏈)。這類不斷呼叫自身的運算形式稱之為遞歸。遞歸可以進一步的分為線性遞歸和數形遞歸。資訊量隨著演算法的輸入呈線性成長的遞歸稱為線性遞歸。計算n!(階乘)就是線性遞歸。因為隨著N的增加,計算所需的時間呈線性成長。另外一種資訊量隨著輸入的增長而進行指數增長的稱之為樹形遞歸。

二、迭代

另外一種計算n!的方式是:先計算1乘以2,再用其結果乘以3,再用的到的結果乘以4….一直乘到N。在程式實作時,可以定義一個計數器,每進行一次乘法,計數​​器都會自增一次,直到計數器的值等於N截至。程式碼如下:

程式碼二

int factorial (int n) {
 int product = 1;
 for(int i=2; i<n; i++) {
  product *= i;
 }
 return product;
}
登入後複製

和程式碼一相比,程式碼二沒有建立一個乘法鏈。在進行每一步計算時,只需要知道當前結果(product)和i的值就可以了。這種計算形式稱為迭代。迭代有這樣幾個條件:1、有一個初始值的變數。 2、一個說明變數值如何更新的規則。 3、一個結束條件。 (循環三要素:循環變數、循環體和循環終止條件)。和遞歸一樣。時間要求隨著輸入的成長呈線性的可以叫做線性迭代。

三、迭代VS 遞歸

比較了兩個程序,我們可以發現,他們看起來幾乎相同,特別是其數學函數方面。在計算n!的時候,他們的計算步數都是和n的值成正比的。但是,如果我們站在程式的角度,考慮他們是如何運作的話,那麼這兩個演算法就有很大不同了。

(註:原文中關於其區別寫的有點扯,這裡就不翻譯了,下面是筆者自己總結內容。)

首先分析遞歸,其實遞歸最大的有點就是把一個複雜的演算法分解成若干相同的可重複的步驟。所以,使用遞歸實現一個計算邏輯往往只需要很短的程式碼就能解決,這樣的程式碼也比較容易理解。但是,遞歸意味著大量的函數呼叫。函數呼叫的局部狀態之所以用堆疊來記錄的。所以,這樣就可能浪費大量的空間,如果遞歸太深的話還有可能導致堆疊溢位。

接下來分析迭代。其實,遞歸都可以用迭代來代替。但相對於遞歸的簡單易懂,迭代就比較生硬難懂了。尤其是遇到一個比較複雜的場景的時候。但是,程式碼的難以理解帶來的有點也比較明顯。迭代的效率比遞歸高,在空間消耗上也比較小。

      遞迴中一定有迭代,但是迭代中不一定有遞歸,且大部分可以互相轉換。

      能用迭代的不要用遞歸,遞迴呼叫函數不只浪費空間,如果遞迴太深的話還容易造成堆疊的溢位。

四、數形遞迴

前面介绍过,树递归随输入的增长的信息量呈指数级增长。比较典型的就是斐波那契数列:

用文字描述就是斐波那契数列中前两个数字的和等于第三个数字:0,1,1,2,3,5,8,13,21……

递归实现代码如下:

int fib (int n) {
 if (n == 0) {
  return 0;
 } else if (n == 1) {
  return 1;
 } else {
  return fib(n-1) + fib(n-2);
 }
}
登入後複製

计算过程中,为了计算fib(5) ,程序要先计算fib(4) fib(3) ,要想计算fib(4) ,程序同样需要先计算 fib(3) fib(2) 。在这个过程中计算了两次fib(3)。

从上面分析的计算过程可以得出一个结论:使用递归实现斐波那契数列存在冗余计算。

就像上面提到的,可以用递归的算法一般都能用迭代实现,斐波那契数列的计算也一样。

int fib (int n) {
 int fib = 0;
 int a = 1;
 for(int i=0; i<n; i++) {
  int temp = fib;
  fib = fib + a;
  a = temp;
 }
 return fib;
}
登入後複製

虽然使用递归的方式会有冗余计算,可以用迭代来代替。但是这并不表明递归可以完全被取代。因为递归有更好的可读性。

以上是Java中的迭代與遞歸實例詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

<🎜>:泡泡膠模擬器無窮大 - 如何獲取和使用皇家鑰匙
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
北端:融合系統,解釋
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
Mandragora:巫婆樹的耳語 - 如何解鎖抓鉤
3 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

熱門話題

Java教學
1666
14
CakePHP 教程
1425
52
Laravel 教程
1328
25
PHP教程
1273
29
C# 教程
1253
24
突破或從Java 8流返回? 突破或從Java 8流返回? Feb 07, 2025 pm 12:09 PM

Java 8引入了Stream API,提供了一種強大且表達力豐富的處理數據集合的方式。然而,使用Stream時,一個常見問題是:如何從forEach操作中中斷或返回? 傳統循環允許提前中斷或返回,但Stream的forEach方法並不直接支持這種方式。本文將解釋原因,並探討在Stream處理系統中實現提前終止的替代方法。 延伸閱讀: Java Stream API改進 理解Stream forEach forEach方法是一個終端操作,它對Stream中的每個元素執行一個操作。它的設計意圖是處

PHP:網絡開發的關鍵語言 PHP:網絡開發的關鍵語言 Apr 13, 2025 am 12:08 AM

PHP是一種廣泛應用於服務器端的腳本語言,特別適合web開發。 1.PHP可以嵌入HTML,處理HTTP請求和響應,支持多種數據庫。 2.PHP用於生成動態網頁內容,處理表單數據,訪問數據庫等,具有強大的社區支持和開源資源。 3.PHP是解釋型語言,執行過程包括詞法分析、語法分析、編譯和執行。 4.PHP可以與MySQL結合用於用戶註冊系統等高級應用。 5.調試PHP時,可使用error_reporting()和var_dump()等函數。 6.優化PHP代碼可通過緩存機制、優化數據庫查詢和使用內置函數。 7

PHP與Python:了解差異 PHP與Python:了解差異 Apr 11, 2025 am 12:15 AM

PHP和Python各有優勢,選擇應基於項目需求。 1.PHP適合web開發,語法簡單,執行效率高。 2.Python適用於數據科學和機器學習,語法簡潔,庫豐富。

PHP與其他語言:比較 PHP與其他語言:比較 Apr 13, 2025 am 12:19 AM

PHP適合web開發,特別是在快速開發和處理動態內容方面表現出色,但不擅長數據科學和企業級應用。與Python相比,PHP在web開發中更具優勢,但在數據科學領域不如Python;與Java相比,PHP在企業級應用中表現較差,但在web開發中更靈活;與JavaScript相比,PHP在後端開發中更簡潔,但在前端開發中不如JavaScript。

PHP與Python:核心功能 PHP與Python:核心功能 Apr 13, 2025 am 12:16 AM

PHP和Python各有優勢,適合不同場景。 1.PHP適用於web開發,提供內置web服務器和豐富函數庫。 2.Python適合數據科學和機器學習,語法簡潔且有強大標準庫。選擇時應根據項目需求決定。

PHP的影響:網絡開發及以後 PHP的影響:網絡開發及以後 Apr 18, 2025 am 12:10 AM

PHPhassignificantlyimpactedwebdevelopmentandextendsbeyondit.1)ItpowersmajorplatformslikeWordPressandexcelsindatabaseinteractions.2)PHP'sadaptabilityallowsittoscaleforlargeapplicationsusingframeworkslikeLaravel.3)Beyondweb,PHPisusedincommand-linescrip

PHP:許多網站的基礎 PHP:許多網站的基礎 Apr 13, 2025 am 12:07 AM

PHP成為許多網站首選技術棧的原因包括其易用性、強大社區支持和廣泛應用。 1)易於學習和使用,適合初學者。 2)擁有龐大的開發者社區,資源豐富。 3)廣泛應用於WordPress、Drupal等平台。 4)與Web服務器緊密集成,簡化開發部署。

PHP與Python:用例和應用程序 PHP與Python:用例和應用程序 Apr 17, 2025 am 12:23 AM

PHP適用於Web開發和內容管理系統,Python適合數據科學、機器學習和自動化腳本。 1.PHP在構建快速、可擴展的網站和應用程序方面表現出色,常用於WordPress等CMS。 2.Python在數據科學和機器學習領域表現卓越,擁有豐富的庫如NumPy和TensorFlow。

See all articles