函数式编程从入门到放弃：递归-->尾递归-->CPS递归

阶乘

递归

FSharp

let rec fact n =
  match n with
  | 0 -> 1
  | x -> x * fact (x-1);;

CPP

int fact(int n){
  if (n = 0){
      return 1;
  }else{
      return n * fact(n-1);
  }
}

尾递归

FSharp

let rec fact_tail n acc = 
  match n with
  | 0 -> acc
  | x -> fact_tail (x-1) (x*acc);;

CPP

int fact_tail(int n,int acc){
  if (n = 0){
   return acc;
  }else{
      return fact_tail(n-1,n*acc)
  }
}

CPS递归

let rec fact_CPS n c =
  match n with
  | 0 -> c 1
  | z -> fact_CPS (z-1) (fun x -> c (x * z));;
fact_CPS 2 id;;
fact_CPS 4 id;;

  fact_CPS 2 id
>>fact_CPS 1 (fun x -> id (x * 2))
>>fact_CPS 0 (fun x -> (fun x -> id (x * 2)) (x * 1))
>>(fun x -> (fun x -> id (x * 2)) (x * 1)) 1
>>(fun x -> id (x * 2) 1
>>id 2
>>2

#include
#include
using namespace std;
void print(int x) {

cout << x << endl;

}
void fact_CPS(int n,function<void(int)> c) {

if (n <= 0) {

c(1);

}

else {

return fact_CPS(n - 1,[n,c](int x) {return c(x * n);});

}

}
int main(void) {

fact_CPS(2,print);

fact_CPS(4,print);

return 0;

}

Fibonacci

let rec fibC n c =
  match n with
  | 0 | 1 -> c n
  | n    -> fibC (n-1) (fun n1 -> fibC (n-2) (fun n2 -> c (n1 + n2)));;

  fibC 2 id
>>fibC 1 (fun n1 -> fibC 0 (fun n2 -> id (n1 + n2)))
>>(fun n1 -> fibC 0 (fun n2 -> id (n1 + n2))) 1
>>fibC 0 (fun n2 -> id (1 + n2)
>>(fun n2 -> id (1 + n2)) 0
>>id (1+0)
>>1