當(dāng)我接觸的F#編程越多，我用到遞歸的可能性就越大，也正是因?yàn)檫@樣，我時(shí)常會(huì)遇到堆棧溢出的問(wèn)題，要想避免堆棧溢出問(wèn)題，Continuation Style Program（CSP）是唯一的方法。以下我們列出普通的遞歸和CSP的版本代碼進(jìn)行對(duì)比，在這里，關(guān)鍵的一點(diǎn)，該方法不會(huì)返回，因此它不會(huì)在調(diào)用的堆棧上創(chuàng)建元素，同時(shí)，由于會(huì)延遲計(jì)算Continuation方法，它不需要被保存在棧元素中：

module FunctionReturnModule =    
   let l = [1..1000000]   
   let rec sum l =    
     match l with   
     | [] -> 0   
     | h::t -> h + sum t   
   sum l 

module CPSModule =    
    let l = [1..1000000]   
    let rec sum l cont =    
      match l with   
      | [] -> cont 0   
      | h::t ->    
        let afterSum v =    
          cont (h+v)   
        sum t afterSum   
    sum l id 

好吧，接下來(lái)的問(wèn)題是如何從普通遞歸的方法得到CSP的遞歸版本呢？以下是我遵循的步驟，記住：其中一些中間代碼并不能通過(guò)編譯。

首先看看我們?cè)嫉倪f歸代碼：

第一步：

module FunctionReturnModule =    
   let l = [1..1000000]   
   let rec sum l =    
     match l with   
     | [] -> 0   
     | h::t ->    
       let r = sum t   
       h + r   
   sum l 

第二步：處理遞歸函數(shù)中的sum，將cont移動(dòng)到afterSum中，afterSum方法獲得到參數(shù)v并將它傳遞給cont(h+v)：

module CPSModule =    
   let l = [1..1000000]   
   let rec sum l cont =    
     match l with   
     | [] -> cont 0   
     | h::t ->    
       let afterSum v =    
         cont (h+v)   
       sum t afterSum   
   sum l id 

那么，接下來(lái)讓我們使用相同的方法來(lái)遍歷樹，下面先列出樹的定義：

type NodeType = int   
type BinaryTree =   
  | Nil   
  | Node of NodeType * BinaryTree * BinaryTree  

最終的結(jié)果如下：

module TreeModule =    
   let rec sum tree =    
     match tree with   
     | Nil -> 0   
     | Node(v, l, r) ->   
       let sumL = sum l   
       let sumR = sum r   
       v + sumL + sumR   
   sum deepTree   
 module TreeCSPModule =    
   let rec sum tree cont =    
     match tree with   
     | Nil -> cont 0   
     | Node(v, l, r) ->   
       let afterLeft lValue =    
         let afterRight rValue =    
           cont (v+lValue+rValue)   
         sum r afterRight   
       sum l afterLeft   
   sum deepTree id 

開始使用相同的步驟將它轉(zhuǎn)換成CSP方式：

首先切入Continuation函數(shù)：

module TreeModule =    
   let rec sum tree cont =    
     match tree with   
     | Nil -> 0   
     | Node(v, l, r) ->   
       let sumL = sum l   
       let sumR = sum r   
       cont (v + sumL + sumR)   
   sum deepTree 

第一步：處理sumR，將cont方法移動(dòng)到afterRight中并將它傳給sum r：

module TreeModule =    
   let rec sum tree cont =    
     match tree with   
     | Nil -> 0   
     | Node(v, l, r) ->   
       let sumL = sum l   
       // let sumR = sum r   
       let afterRight rValue =     
         cont (v + sumL + rValue)   
       sum r afterRight   
   sum deepTree 

第二步：處理sumL：

module TreeModule =    
   let rec sum tree cont =    
     match tree with   
     | Nil -> 0   
     | Node(v, l, r) ->   
       //let sumL = sum l   
       let afterLeft lValue =   
         let afterRight rValue =     
           cont (v + lValue + rValue)   
         sum r afterRight   
       sum l afterLeft   
   sum deepTree 

結(jié)束了，接下來(lái)讓我們用下面的代碼進(jìn)行測(cè)試吧：

let tree n =    
  let mutable subTree = Node(1, Nil, Nil)   
  for i=0 to n do   
    subTree <- Node(1, subTree, Nil)   
  subTree   
let deepTree = tree 1000000