FP & Recursive Presentation

是个抛砖引玉，javascript语法

示例

斐波那契数列

img

据说斐波那契研究斐波那契数列就是从兔子的繁殖问题开始研究的。

递归定义

递归，就是在运行的过程中直接或间接调用自己。

main() {
  main()
}

递归数据结构

存在部分数据的结构和整体结构是一致的
存在最小的结构，作为数据结束
例：

enum Tree<T> {
    case empty
    indirect case node(T, Tree<T>, Tree<T>)
}

递归算法

问题能够被分解成更小的具有同样性质的问题
问题有中止条件
例：

$Fib(n) = \left\{ \begin{array}{ll} 1 & \textrm{n < 2，这里就是中止条件}\\ Fib(n-1) + Fib(n-2) & \textrm{n>=2，把问题拆解成两个小问题，不断朝中止条件逼近}\\ \end{array} \right.$

反例：3n+1猜想

$f(n) = \left\{ \begin{array}{ll} f(n/2) & \textrm{n为偶数}\\ f(3n + 1) & \textrm{n为奇数}\\ 1 & \textrm{n==1}\\ \end{array} \right.$

应用场景

数据结构是递归的
计算过程可以归纳
- 二分法

例子

后面的代码不加说明都是javascript代码

//二叉树前序遍历 
let traversePre = node => 
    node == null ? [] 
                   : [node.value, 
                  ...traversePre(node.left), 
                  ...traversePre(node.right)]

//链表分拆，把链表`a->b->c->d->e`拆分成两个，奇数序的一个，偶数序的一个
//结果应该是`a->c->e`和`b->d`
let splitList = head =>
  head == null ? [null, null]
               : ([s0,s1] = splitList(head.next),
                 head.next = s1,
                 [head, s0])

斐波那契数列算法对比

//非递归 fib 1
let fib = n => {
  var prev = 1, curr = 1
  while (n-- > 1) {
    [prev, curr] = [curr, prev+curr]
  }
  return curr
}

//递归 fib 2
let fib = n =>
  n < 2 ? 1
        : fib(n-1) + fib(n-2)

从逻辑上看，非递归的版本要关注的比较多，更容易出bug，递归版本则更接近问题本身的描述，很难出bug

Recursive function in C or something else...

缺点

调用堆栈容易溢出
- 本机测试python 调用堆栈的深度只有998
性能不好
- 需要分配调用堆栈，函数调用开销大
重复计算
- DP
...

优点

容易理解
代码复杂度低，代码量少
- bug少

函数式编程中的递归

没有循环，只有递归
纯函数
- 消除重复计算

尾递归 tail recursive

尾递归是一种递归的特殊形式，递归调用之后立即返回

可以通过编译器优化，使用goto替代call，消除调用堆栈

//尾递归
let gcd = (m, n) =>
  0 == n ? m
         : gcd(n, m%n)

//非尾递归
let fac = n =>
  0 == n ? 1
         : n * fac(n-1)

循环转换成尾递归

let fac = n => {
  var fac = 1
  while(n)
    fac = fac * n--
  return fac
}

分析一下n=6的时候while循环

n	fac
6	1
5	6
4	6 * 5
3	6 * 5 * 4
2	6 * 5 * 4 * 3
1	6 * 5 * 4 * 3 * 2
0	6 * 5 * 4 * 3 * 2 * 1
	return

分析循环中所有的状态，提取到参数里面，基本上就可以形成尾递归的算法

let _fac = (n, temp) =>
  n == 0 ? temp
         : _fac(n-1, n * temp)
let fac = _fac(n, 1)

再如上面提到的fib的非递归算法，分析如下：fib(5)

n	prev	curr
5	0	1
4	1	1
3	1	2
2	2	3
1	3	5
0	5	8
		return

// fib 3
let _fib = (n, prev, curr) =>
  n == 0 ? curr
         : _fib(n-1, curr, prev + curr)
let fib = n => _fib(n, 0, 1)

一般队列求值

$L_n = \left\{ \begin{array}{ll} f(L_{n-1}) & L_n\textrm{可以通过}L_{n-1}\textrm{求值}\\ L_1 & L_1\textrm{是已知的}\\ \end{array} \right.$

在factorial队列中，有 $L_n = n * L_{n-1}$ ， $L_1 = 1$

对于Fibonacci队列，直观看起来没有这样的公式，不过我们可以转换一下，设 $L_n = (fib_n,\ fib_{n+1})$

则可以得到 $L_{n+1} = (fib_{n+1},\ fib_{n+2}) = (L_n.second,\ L_n.first + L_n.second)$

// fib 4-1
let fib_class = {
  init: [0,1],
  next: ([first, second]) => [second, first + second]
}
let _fib = (n, prev) =>
  n == 0 ? prev
         : _fib(n-1, fib_class.next(prev))
let fib = n => _fib(n, fib_class.init)

// fib 4-2
let _fib = (n, [prev, curr]) =>
  n == 0 ? curr
         : _fib(n-1, [curr, prev + curr])
let fib = n => _fib(n, [0, 1])[1]

Question:

如何实现一个queueFactory可以使let fib = queueFactory(fib_class)

CPS continuation pass style

一种编程机制，函数没有返回值，得到结果后的下一步需要传入一个函数

//普通函数
let user = getUser()
validUser(user)
//CPS
getUser(validUser)

CPS + tail recursive

一般来讲，CPS都和尾递归一起使用，中间状态实际上是对cont函数的不断递归

let _fac = (n, cont) => 
  n == 1 ? cont(1)
         : _fac(n-1, r => cont(n * r))
let fac = n => _fac(n, r=>r)

//swift 
func _fac(_ n:Int, cont: (Int)->()) {
  if n == 1 {
    cont(1)
  } else {
    _fac(n-1) {
      cont( $0 * n)
    }
  }
}

代码解读：

如果n==1，程序结束，调用continuation，结果为1

如果n > 1，假如我们计算了fac(n-1)结果是r，那么最终的结果是n*r，通过continuation返回

代入n=4，展开整个调用

n	cont	简化cont
4	Log
3	r1 => (r => r) (4 * r1)	r1 => log(4 * r1)
2	r2 => [ r1 => (r => r)(4 * r1) ] (3 * r2)	r2 => log(4 * 3 * r2)
1	r3 => { r2 => [ r1 => (r => r)(4 * r1) ] (3 * r2) } (2 * r3)	r3 => log(4 * 3 * 2 * r3)
	cont(1)代入后得到最终结果log(24)

reduce实现

let reduce = (arr, init, func) => {
  for(item of arr) {
    init = func(init, item)
  }
  return init
}
//[1,2,3,4],head = 1; tail = [2,3,4]
let reduce1 = ([head, ...tail], prev, func) => 
   head == null ? prev
                : reduce1(tail, func(prev, head), func)

//f(L0,...f(Ln-2,f(Ln-1,f(Ln, I))))
let reduceR = ([head, ...tail], init, func, cont) =>
  head == null ? cont(init)
               : reduceR(tail, init, func, prev => cont(func(prev, head)))

//test
reduce1([1,2,3],0,(a,b)=>a+b)
reduceR([1,2,3],0,(a,b)=>a*10+b,console.log)

尾递归和Reduce

let x = [1,2,3,4,5,6]
//fac
x.reduce((p, c) => p * c, 1)
//fib 8
x.reduce(([p, c]) => [c, p + c], [0, 1])[1]

Fibonacci CPS1

// fib 5
let _fib = (n, cont) =>
  n == 0 ? cont([0,1])
         : _fib(n-1, ([prev, curr]) => cont([curr, prev + curr]))
let fib = n => _fib(n, r=>r)[1]

Fibonacci CPS 2

//fib 6
let _fib = (n, cont) =>
  n == 0 ? cont(1)
 :n == 1 ? cont(1)
         : _fib(n-1, r => cont(r + _fib(n-2, r=>r)))
                
let fib = n => _fib(n, r=>r)

Question

把前序遍历二叉树的代码改造成尾递归或者CPS

Trampoline

非函数式语言解决递归的调用堆栈叠加的问题

let trampoline = f => {
  do {
    f = f()
  } while(typeof f === 'function')
  return f
}
// fib 7
let _fib = (n, cont) =>
    n == 0 ? cont(1)
   :n == 1 ? cont(1)
           : _fib.bind(null,n-1, r => cont(r + fib(n-2)))
           
let fib = n => trampoline(_fib.bind(null,n, r=>r))

FP & Recursive 递归