F#中用Continuation编程避免堆栈溢出

当我接触的F#编程越多，我用到递归的可能性就越大，也正是因为这样，我时常会遇到堆栈溢出的问题，要想避免堆栈溢出问题，Continuation Style Program（CSP）是唯一的方法。以下我们列出普通的递归和CSP的版本代码进行对比，在这里，关键的一点，该方法不会返回，因此它不会在调用的堆栈上创建元素，同时，由于会延迟计算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

好吧，接下来的问题是如何从普通递归的方法得到CSP的递归版本呢？以下是我遵循的步骤，记住：其中一些中间代码并不能通过编译。

首先看看我们原始的递归代码：

第一步：

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

第二步：处理递归函数中的sum，将cont移动到afterSum中，afterSum方法获得到参数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

那么，接下来让我们使用相同的方法来遍历树，下面先列出树的定义：

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

最终的结果如下：

 
 
  
  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

开始使用相同的步骤将它转换成CSP方式：

首先切入Continuation函数：

 
 
  
  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方法移动到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

结束了，接下来让我们用下面的代码进行测试吧：

 
 
  
  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

本文名称：F#中用Continuation编程避免堆栈溢出
文章位置：http://www.mswzjz.cn/qtweb/news32/71032.html

攀枝花网站建设、攀枝花网站运维推广公司-贝锐智能，是专注品牌与效果的网络营销公司；服务项目有等

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：贝锐智能

贝锐智能技术为您推荐以下文章