模擬狀態機消除遞歸心得

04-17

在之前的「求字元串最長不連續迴文序列的深入研究「文章里我使用了性能欠佳的遞歸來解決問題，後為了達到消除遞歸的目的在網上看到了使用模擬狀態機方法消除，感覺很不錯，學習之後在這裡進行一下總結。

其實這個方法很簡單，主要步驟如下：

寫出遞歸函數
根據遞歸函數畫出狀態機流程圖，除了起止節點，將其他節點標序號
根據狀態機創建Context類
定義狀態機方法

介紹一下Context對象：

狀態機中，會充斥著各種各樣的條件（C），每個條件對應Context的一個返回boolean類型的方法，另外遞歸函數中同時充斥著上下文相關的變數（就是jvm局部變數表用到的那些），這些變數都要放到Context里作為成員變數。

Context還需要有parent引用，用來模擬出棧入棧（當然可以用真正的棧，就不需要parent引用了），還需要一個baby方法，返回新的Context對象並將this賦予新的parent，用來模擬入棧（同樣也可以使用真正的棧來替代）

接下來舉幾個例子來說明如何使用這種方法消除遞歸。

遞歸求階乘

1.寫出遞歸函數

def f( n : Int ) : Int = { if( n == 1 ) 1 else { val t = f( n - 1 ) t * n } }

2.根據遞歸函數畫出狀態機流程圖，並標號

其實狀態圖很簡單，就是找條件找條件找條件。。。遇到遞歸就入棧，遇到return就判斷棧空

上圖中：

狀態1.C1對應代碼中的n==1

狀態2.C2對應棧空（用對應於Context的parent==null）

Act1對應於t * n，也就是出棧拿到子上下文結果t後，使用t做一些事情

狀態3.上下文入棧（包裝）對應於調用f（n-1），在這裡創建新Context對象

狀態4.上下文出棧（拆裝）用來模擬出棧返回結果

3.根據狀態機創建Context類：

case class Context(parent : Context , n : Int , var result : Int){ def c1() = n == 1 def c2() = parent == null def act1(resultFromChild : Int) = result = resultFromChild * n def baby : Context = Context( this , n - 1 , 1 )}

4.根據狀態機創建狀態機方法：

def stateMachine( _ctx: Context ): Int = { var (ctx, stateNum) = (_ctx , 1 ) while( stateNum != -1 ){//-1 退出 stateNum match { case 1 => stateNum = if( ctx.c1 ) 2 else 3 case 2 => stateNum = if( ctx.c2 ) -1 else 4 case 3 => ctx = ctx.baby stateNum = 1 case 4 => ctx.parent.act1( ctx.result ) ctx = ctx.parent stateNum = 2 case _ => } } ctx.result}

6.客戶端調用：

def main(args: Array[String]): Unit = { println( stateMachine( Context( null , 10, 1 ) ) )}

下面看一個複雜一點的，快速排序：

1.遞歸函數：

def sort( low : Int , high : Int , arr : Array[Int] ) : Unit ={ var ( l , h , p ) = ( low , high , arr( low ) ) while( l < h ){ while ( l < h && arr( h ) >= p ) h -= 1 if( l < h ) swap( l , h , arr ) while( l < h && arr( l ) <= p ) l += 1 if( l < h ) swap( l , h , arr ) } if( l > low ) sort( low , l - 1 , arr ) if( h < high ) sort( l + 1 , high , arr )}def swap(i: Int, j: Int, arr: Array[Int]) = { val t = arr(i) arr(i) = arr(j) arr(j) = t}

可以看到在sort裡面兩處調用遞歸，這個時候在出棧處理的時候有些不同

2.畫出狀態圖：

在有多處調用遞歸的時候，Context需要新加一個callsite成員，這樣恢復上下文後，調用ctx的route方法判斷下一狀態是多少

3.創建Context類：

case class Context( var parent : Context, var l : Int , var h : Int, var low : Int , var high : Int, var callsite : Int ) { override def clone(): AnyRef = Context(parent,low,high,low,high,callsite) //條件，c1,c2,c3...太多，這裡寫到一起 def c(i : Int) : Boolean = i match { case 1 => l < h case 2 => c( 1 ) && arr( h ) >= arr( low ) case 3 => c( 1 ) case 4 => c( 1 ) && arr( l ) <= arr( low ) case 5 => c( 1 ) case 6 => l > low case 7 => h < high case 8 => parent == null } //同理，寫到一起 def act(i : Int) : Unit = i match { case 1 => h -= 1 case 2 => swap( l , h , arr ) case 3 => l += 1 case 4 => act( 2 ) } def route = callsite match { case 6 => 7 case 7 => 8 } def baby(callsite : Int) : Context= { val res = this.clone.asInstanceOf[Context] res callsite_= callsite res parent_= this callsite match { case 6 => res high_= l - 1 res h_= l - 1 case 7 => res low_= l + 1 res l_= l + 1 } res } }

4.創建狀態機

def stateMachine( _ctx: Context ): Unit = { var (ctx, nextState , callsite) = (_ctx , 1 , 0) //如果滿足，則轉到ify狀態，否則轉到ifn狀態 def ~~ ( ynum : Int , nnum: Int , ify : => Any = None , ifn : => Any = None ) ={ val y = ctx c nextState if( y ) ify else ifn nextState = if( y ) ynum else nnum } while( nextState != -1 ){//-1 退出 nextState match { case 1 => ~~ ( 2 , 6 ) case 2 => ~~ ( 2 , 3 , ctx act 1 ) case 3 => ~~ ( 4 , 4 , ctx act 2 ) case 4 => ~~ ( 4 , 5 , ctx act 3 ) case 5 => ~~ ( 1 , 1 , ctx act 4 ) case 6 => ~~ ( 10 , 7 , callsite = 6) case 7 => ~~ ( 10 , 8 , callsite = 7) case 8 => ~~ ( -1 , 9 ) case 9 => nextState = ctx.route ctx = ctx.parent case 10 => ctx = ctx baby callsite nextState = 1 case _ => } }}

5.客戶端調用

var arr : Array[Int] = _def main(args: Array[String]): Unit = { arr = Array(2,3,5,1,6) stateMachine( Context(null , 0 , arr.length - 1 , 0 , arr.length - 1 , 0) ) println( arr toList )//List(1,2,3,5,6)}