FP & Recursive Presentation
是个抛砖引玉，javascript语法
示例
斐波那契数列
img
据说斐波那契研究斐波那契数列就是从兔子的繁殖问题开始研究的。
递归定义
递归，就是在运行的过程中直接或间接调用自己。
main() {
main()
}
递归数据结构
- 存在部分数据的结构和整体结构是一致的
- 存在最小的结构，作为数据结束
- 例：
enum Tree<T> {
case empty
indirect case node(T, Tree<T>, Tree<T>)
}
递归算法
- 问题能够被分解成更小的具有同样性质的问题
- 问题有中止条件
- 例：
- 反例：3n+1猜想
应用场景
- 数据结构是递归的
- 计算过程可以归纳
- 二分法
例子
后面的代码不加说明都是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)
一般队列求值
在factorial队列中，有，
对于Fibonacci队列，直观看起来没有这样的公式，不过我们可以转换一下，设
则可以得到
// 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))
网友评论