遞迴與迴圈
對於不同型別的需要重複計算的問題,迴圈與遞迴兩種方法各有所長,能給出較直觀簡單的方案。另一方面,循環和遞歸的方法可以互相轉換。任何一個循環的程式碼都可以用遞歸改寫,實現相同的功能;反之亦然。在不失去其普遍性的前提下,可以把循環和遞歸分別用下列偽代碼概括。
偽程式碼格式說明:迴圈採用while形式;變數不加定義;賦值用:=;條件式和執行的語句都寫成函數的形式,圓括號內寫上相關的值。其他語法方面,盡量接近Javascript的規格。
//pseudo code of a loop //while形式 function loop(arguments){ //结果的初始值 result:=initial_value; while(condition(variable, arguments)){//循环条件,可能只需arguments,也可能为了方便引入循环变量 //计算结果。参数包括之前的结果、当前循环变量和外部变量 result:=calculate(result, variable, extern_variables); //影响函数的外部环境,即修改外部变量 changeStatus(result, variable, extern_variables); //执行完循环体中的语句后,修改参数或循环变量。 modify_arguments_variable(arguments, variable); } //返回结果 return result; }
同樣我們給出遞歸函數的偽代碼。
//pseudo code of a recursion function recursion(arguments){ //以下代码为控制函数重复调用的结构部分。 //获得再次调用此函数的新的参数,可能为多组arguments值。 //对应于循环中的condition(variable, arguments)和modify_arguments_variable(arguments, variable)。 new_arguments:=conditional_get_next(arguments); //对新参数的每一组,调用函数自身。 results:=recursion(new_arguments); //以下的代码为每次调用都运行的功能部分 //计算结果。涉及到之前的结果、当前循环变量和外部变量。 //对应于循环中的result:=calculate(result, variable, extern_variables)。 result:=calculate(arguments, extern_variables); result:=combine(result, results); //影响函数的外部环境,即修改外部变量 changeStatus(result, arguments, extern_variables); return result; }
籍比較兩段程式碼,可以看出循環和遞歸有相似的構成,透過改變順序和適當的變換,任何循環都可以用遞歸的方式實現。程序簡單時,這種轉換很容易看出。例如下面這個簡單的累計求和函數:
//loop function sum(num){ var result=1; while (num>1){ result+=num; num--; } return result; }
對應的遞迴形式:
//recursion function sum2(num){ if (num>1){ return num+sum(num-1); }else{ return 1; } }
反之,大部分遞迴程式也可以直接由迴圈來實現。下面是求最大公約數的循環形式的函數。
function gcd2(a, b){ var temp; if (a<b){ temp=a; a=b; b=temp; } var c=a%b; while (c!==0){ a=b; b=c; c=a%b; } return b; }
不過,從遞迴到循環的轉換並不是都這麼容易。遞歸偽程式碼中的產生再次呼叫此函數的新參數部分
new_arguments:=conditional_get_next(arguments);
較之循環的對應部分更為靈活。可以依照新產生的參數組數(函數所需的所有參數為一組)將遞歸分為兩類。第一類為參數組數固定,此遞歸可以轉換為循環,例如斐波那契數列和最大公約數的例子;第二類為參數組數不確定——就像在遍歷一個圖或樹的時候那樣,每個點都有任意個相鄰的點-該遞迴不能直接轉換為迴圈。
因為循環只能做一維的重複,而遞歸可以遍歷二維的結構。例如一棵樹中,一個節點既有它的子節點,也有同級的節點,簡單的一維循環不能夠在兩個方向上遍歷。 但是如果我們在循環中藉助某種資料結構記住有關節點位置的一些信息,第二類遞歸也可以用循環實現。
歸納起來。所有循環都可以用遞歸實現;所有遞歸都可以用循環實現。採用哪一種方法,由具體問題下哪一種思路較方便直覺和使用者的喜好決定。
#以上是JavaScript的遞迴與循環各自的優點程式碼詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章!