以前我很少写递归,因为感觉写递归需要灵感,很难复制。
学了点函数式后,我发现写递归其实是有套路的。
递归只需要想清楚 2 个问题:
const has = (element, arr) => {};
什么情况不需要计算?
数组为空时不需要计算,一定不包含。
const has = (element, arr) => { if (arr.length === 0) return false; };
怎么把大问题变成小问题?
把 arr
的长度减小,向数组为空的情况逼近。
从 arr
中取出第一个元素和 element
比较:
true
。const has = (element, arr) => { if (arr.length === 0) return false; else if (arr[0] === element) return true; else return has(element, arr.slice(1)); };
const del = (element, arr) => {};
什么情况不需要计算?
数组为空时不需要计算,返回空数组。
const del = (element, arr) => { if (arr.length === 0) return []; };
怎么把大问题变成小问题?
把 arr
的长度减小,向空数组的情况逼近。
从 arr
中取出第一个元素和 element
比较:
const del = (element, arr) => { if (arr.length === 0) return []; else if (arr[0] === element) return arr.slice(1); else return [ arr[0], ...del(element, arr.slice(1)) ]; };
阶乘、斐波那契用递归来写也是这个套路,代码结构都是一样的。
先列出不需要计算的情况,再写大问题和小问题的转换关系。
const factorial = n => { if (n === 1) return 1; else return n * factorial(n - 1); };
const fibonacci = n => { if (n === 1) return 1; else if (n === 2) return 1; else return fibonacci(n - 1) + fibonacci(n - 2); };
小孩子用数数的方式做加法,过程是这样的:
3 颗糖 加 2 颗糖 是几颗糖?
小孩子会把 3 颗糖放左边,2 颗糖放右边。
从右边拿 1 颗糖到左边,数 4,
再从右边拿 1 颗糖到左边,数 5,
这时候右边没了,得出有 5 颗糖。
这也是递归的思路。
const add = (m, n) => {};
当 n = 0
时,不需要计算,结果就是 m
。
const add = (m, n) => { if (n === 0) return m; };
把问题向 n = 0
逼近:
const add = (m, n) => { if (n === 0) return m; else return add(m + 1, n - 1); };
当然
m = 0
也是不需要计算的情况。
选择m = 0
还是n = 0
作为不需要计算的情况 决定了 大问题转成小问题的方向。
const add1 = m => m + 1;
把 add1
的返回结果乘 2,通常这么写:
add1(5) * 2;
用 continuation passing style
来实现是这样的:
const add1 = (m, continuation) => continuation(m + 1); add1(5, x => x * 2);
add1
加一个参数 continuation
,它是一个函数,表示对结果的后续操作。
我们用 continuation passing style
来写写递归。
以下用
cps
代替 continuation passing style
cont
代替 continuation
const factorial = (n, cont) => { if (n === 1) return cont(1); else return factorial(n - 1, x => cont(n * x)); };
n === 1
,把结果 1
交给 cont
;n > 1
,计算 n - 1
的阶乘,n - 1
阶乘的结果 x
乘 n
,交给 cont
。这个
factorial
函数该怎么调用呢?
cont
可以传x => x
,这个函数接收什么就返回什么。factorial(5, x => x);
之前的写法:
const factorial = n => { if (n === 1) return 1; else return n * factorial(n - 1); };
递归调用 factorial
不是函数的最后一步,还需要乘 n
。
因此编译器必须保留堆栈。
新写法:
const factorial = (n, cont) => { if (n === 1) return cont(1); else return factorial(n - 1, x => cont(n * x)); };
递归调用 factorial
是函数的最后一步。
做了尾递归优化的编译器将不保留堆栈,从而不怕堆栈深度的限制。
也就是说:可以通过 cps
把递归变成尾递归。
const fibonacci = (n, cont) => { if (n === 1) return cont(1); else if (n === 2) return cont(1); else return fibonacci(n - 1, x => fibonacci(n - 2, y => cont(x + y)) ); };
n === 1
,把结果 1
交给 cont
;n === 2
,把结果 1
交给 cont
;n > 2
,n - 1
的结果 x
,n - 2
的结果 y
,x + y
交给 cont
。cps
可以把递归变成尾递归,但并不是用了 cps
的递归就是尾递归。
像这么写,就不是尾递归:
const fibonacci = (n, cont) => { if (n === 1) return cont(1); else if (n === 2) return cont(1); else return fibonacci(n - 1, x => cont(fibonacci(n - 2, y => x + y)) ); };
注意这段代码:
x => cont(fibonacci(n - 2, y => x + y));
fibonacci
的调用不是函数的最后一步,cont
的调用才是最后一步。
不管按以前的方式写递归 还是 用 cps
写递归,思想都是一样的,都是要搞清:
如对本文有疑问, 点击进行留言回复!!
selenium + ajax抓取英雄联盟全部英雄的详细信息及多线程保存全部皮肤图片到本地
网友评论