关于函数递归和迭代的转化, 及尾递归相关知识的接触和思考
javascript实现数据结构： 树和二叉树,二叉树的遍历和基本操作
js 二叉树
【数据结构与算法】深入浅出递归和迭代的通用转换思想
经典算法｜递归和递归消除的迭代法
我总是怀疑, 我是不是能学好编程.
我似乎总是会跑到某种奇怪的地方上去,
消耗很多时间, 像是在浪费, 又像是有价值.
网上说, 大多数的迭代,和递归是可以互相转化的.
从形式上这两者是非常不同的.
我们试着去寻找, 这两者都需要的概念,在这两者身上是如何体现的.
当然我最初的目的是,
希望能够很建议,起码思路很清晰的能够把我遇到的,
迭代能够转换成递归,
同理能够把递归转换成 迭代.
我们先看最简单的循环
while(true) {
console.log(1)
}
这是个死循环, 这里没有一个变量,
但这里拥有三个概念,
1. 循环
2. 循环条件, 即 true
3. 执行代码 , 即 console.log(1)
改成 递归 则是
function go () {
console.log(1);
go();
}
我相信这是个递归函数, 并且效果和上面的while循环相似.
把上面对应的概念在这里寻找一下
1. 循环, 函数自身调用体现了循环
2. 循环条件, 似乎在这里没有体现, 那我们可以稍微改一下
3. 执行代码, 即 console.log(1)
为了体现 循环条件 我们改一下
function go () {
console.log(1);
if (true) {
go();
}
}
上面这两个代码, 语法上都没毛病, 概念也都没毛病.
那么第二个问题, 上面的代码, 明显是死循环,
我们大多时候希望的不是死循环.
一个代码想要避开死循环, 需要什么?
需要两个概念, 一个是开启循环, 一个是 关闭循环.
而想要实现这个事情, 就必须要从循环条件入手.
但这个条件本身要有两个状态,
这很明显啊, 如果只有一个状态, 要么无法开启, 要么就一直循环.
换言之, 条件必须是一个变量.
var flag = true;
while(flag) {
console.log(1);
}
function go () {
console.log(2);
if (flag) {
go();
}
}
理论上来讲, 这个flag, 可以在循环体外面更改,
也可以在循环体内部更改.
在外部
var flag = true;
while(flag) {
console.log(1);
}
function go () {
console.log(2);
if (flag) {
go();
}
}
flag = false;
但可能会发现不会像预期那样停止循环.
电脑会因为死循环 导致卡机, 无法接收执行 flag = false 的语句
在内部
var flag = true;
while(flag) {
console.log(1);
flag = false;
}
function go () {
console.log(2);
flag = false;
if (flag) {
go();
}
}
一般情况下(至少作为一个小白我遇到的大多数情况), 我们会设置成在内部控制循环条件.
不过像上面这种, 刚开启就结束的循环, 似乎很难称得上循环.
你可能会想, 这逼是有毛病吧, 净扯些没用的循环, 或者算不上循环.
那我们开始说一些我们常见的循环.
遍历输出一个数组
var arr = [1,2,3];
for(var i = 0; i < arr.length, i++){
console.log(arr[i])
}
首先我们要理解, 所有的for 循环, 都可以改成 while循环
var i = 0;
while(i < arr.length){
console.log(arr[i]);
i++;
}
如果我们改成上面那种flag 方式, 也可以
var flag = true;
var i = 0;
while(flag) {
console.log(arr[i]);
i++;
if(i >= arr.length) {flag = false}
}
反正先有一个信心是, 所有的for循环,都可以转成 while + flag 这种形式
换句话来讲, 作为循环的条件变量, 可以不是flag, 任何其他的变量都有可能.
试着改成递归,然后发现, 有了变量,参数之后, 有两种基本选择
第一种, 变量和参数放在全局当中
var arr = [1,2,3];
var i = 0;
function diedai () {
console.log(arr[i])
i++;
if (i < arr.length) {
diedai();
}
}
第二种, 每次调用,都传递进去
function diedai (arr,i) {
var arr = arr || [];
var i = i || 0;
console.log(arr[i])
i++;
if (i < arr.length) {
diedai(arr,i);
}
}
diedai(arr);// 我们要把数据传进去.
其实这种情况, 我本人最快联想到的是arr.forEach() 方法
我们模拟一下forEach
var arr = [1,2,3];
function cb (item) { console.log(item)};
function forEach (arr,cb) {
var len = arr.length;
for(var i = 0; i < len ; i++) {
cb(arr[i])
}
}
forEach(arr,cb)
我们试着改成 递归,
根据上面的说法, 有两种方案
第一种, 变量放在全局
function forEach (arr,cb) {
var arr = arr;
var cb = cb;
var len = arr.length;
var i = 0;
/ 实际上, 真正完成递归的是函数go() 只是所有的变量,都放在了父级上
function go () {
cb(arr[i]);
i++;
if (i < len) {
go();
}
}
go()
}
第二种, 变量传递
function forEach (arr,cb,i) {
var i = i || 0;// 除了初始值, 其他都是传进来的值
cb(arr[i++]);
if (i < arr.length) {
forEach(arr,cb,i);
}
}
从某种角度来讲, 无论是递归,还是迭代,
除了要解决算法问题之外, 其实要考虑的是, 如何存值的问题.
递归方式之所以看似有两种, 是因为,
1. 函数内部可以访问函数外部的变量,并改变函数外部的变量.
2. 函数内部可以覆盖函数外部的变量.
虽然上面的递归是递归, 因为确实是函数自身调用,
但似乎感觉和我们常见的递归相比差点什么,
主要是, 我们的递归虽然能够完成循环,
但每个函数似乎都没有返回值,
或者说, 没有利用返回值
我们模拟下reduce 来感受一下
迭代版本
var arr = [1,2,3];
function add (a,b) {
return a + b;
}
function reduce (arr,cb,init) {
if (typeof init == "undefined") {
var i = 1;
var init = arr[0];
}else{
var i = 0;
var init = init;
}
for(; i < arr.length; i++) {
init = cb(init,arr[i],i,arr)
}
return init
}
reduce(arr,add)/ 6
递归版本1, 参数都放在 全局上
function reduce (arr,cb,init) {
if (typeof init == "undefined") {
var i = 1;
var init = arr[0];
}else{
var i = 0;
var init = init;
}
function go () {
init = cb(init,arr[i],i,arr);
i++;
if (i < arr.length) {
go();
}
}
go()
return init;
}
reduce(arr,add)/ 6
递归版本2
function reduce (arr,cb,init,i) {
if (typeof init == "undefined") {
var i = i || 1;
init = arr[0];
}else{
var i = i || 0;
init = init;
}
if (i < arr.length) {
init = cb(init,arr[i],i,arr);
i++;
init = reduce(arr,cb,init,i)
return init;
}else {
return init
}
}
稍微简化一下,尽管根本没有简化的效果
function reduce (arr,cb,init,i) {
if (typeof init == "undefined") {
var i = i || 1;
init = arr[0];
}else{
var i = i || 0;
init = init;
}
if (i < arr.length) {
return reduce(arr,cb,cb(init,arr[i],i,arr),i + 1)
}else {
return init
}
}
在把迭代转换成 递归的时候, 我的思路究竟都发生了些什么?
实际上,但从上面两个例子当中,感觉 递归版本1 跟 迭代基本没什么区别.
主要就是递归版本2,区别比较明显.
这要怎么描述呢?
版本1 当中, 函数的感觉就是一段代码的执行,
版本2 当中, 函数的感觉其实代表的是一个值的,
我觉得例子举得不太恰当.
还是累加问题
迭代版本
function add (n) {
var sum = 0;
for(var i = 0; i <= n ; i++) {
sum = sum + i;
}
return sum;
}
递归版本
function add (n) {
if (n == 0) {
return 0
}
// add(n) = n + add(n - 1);
return (n + add(n - 1));
}
感觉这么比较似乎还是不太好,
因为从例子上来看, 迭代版本采取的是从0递增
而递归版本是从n 递减,
我们加一下
迭代版
function add (n) {
var sum = 0;
for(;n--;){
sum = sum + n
}
}
递归版
function add (n,i) {
var i = i || 0;
if (i == n) {
return n
}
// add(n,i) = add(n,i + 1) + i
return add(n,i + 1) + i
}
哇塞, 我自己都被自己秀到了,有没有?
当然如果我们套用之前递归版本还可以这样
套用之前的递归版本1
function add (n) {
var sum = 0;
var i = 0;
function go () {
sum = sum + i;
i++;
if (i <= n) {
go()
}
}
go();
return sum
}
套用之前的递归版本2
function add (n,sum,i) {
var sum = sum || 0;
var i = i || 0;
sum = sum + i;
i++;
if (i <= n) {
sum = add(n,sum,i)
}
return sum
}
哈哈哈哈哈哈哈哈哈
有没有觉得很搞笑?
我感觉,自己整理不下去了, 感觉好难整理思路.每次都是这样.
首先, 比较这个套用了递归版本2 和最上面的递归版本,
能感觉两者的差异很大.
从形式上来讲, 递归原版比这个版本2 要简洁非常多.
为什么会这样呢?
因为原版的思路是从关系入手的.
即,n之累加和 等于 n + (n-1)之累加.
重点体现的是这一关系.
而这种思路, 应该算是数学上的归纳法思路的实现?
而递归版本2 的思路其实是 迭代版本的 思路体现,
或者概念体现.
即, 迭代版本中, 我们需要的变量, 我们在递归时, 想要全部用上,
所以才会造成这种代码.
客观来讲, 递归版本2 是可以简化到 递归原版的.
我们来试着简化一下
从这里
function add7 (n,sum,i) {
var sum = sum || 0;
var i = i || 0;
sum = sum + i;
i++;
if (i <= n) {
sum = add7(n,sum,i)
}
return sum
}
到这里
function add8 (n,i) {
var i = i || 0;
if (i < n) {
i = add8(n,i + 1) + i
}
return i
}
天哪, 你看到了没?
我简直不敢想象.
这肯定是一种简化, 一种合理的简化,
根据等号进行的简化.
我之所以不敢想象是因为, 对于递归结构的函数,
我压根生不起想要简化的念头, 因为很容易让我脑瓜疼
这里的return 也可以看成是 =
因为与sum 有关的 = 都可以进行整理
首先是
sum = sum + i;和
sum = add7(n,sum,i)
可以直接合成
sum = add7(n,sum,i) + i;
但问题是, 中间有个 i++, 即, 两个i 的值是不同的, 所以
sum = sum + i;
i++;
sum = add7(n,sum,i)
这三句可以合成为
sum = add7(n,sum,i + 1) + i;
此时的函数是这样的
function add7 (n,sum,i) {
var sum = sum || 0;
var i = i || 0;
if (i <= n) {
sum = add7(n,sum,i + 1) + i
}
return sum
}
从形式上来讲, i 完全可以代替 sum
所以就变成了
function add8 (n,i) {
var i = i || 0;
if (i < n) {
i = add8(n,i + 1) + i
}
return i
}
不过有个细节是, i <= n 要改成 i < n
我试着简化成这样
function add8 (n,i) {
var i = i || 0;
if (i < n) {
return add8(n,i + 1) + i
}
}
结果不行,
因为当 i >= n 时 返回的是 undifined
必然导致所有结果要么是 undifined, 要么是 NaN
应该改成这样
function add8 (n,i) {
var i = i || 0;
if (i < n) {
return add8(n,i + 1) + i
}else{
return n
}
}
然后对if 条件进行 转换就变成
function add8 (n,i) {
var i = i || 0;
if (i >= n) {
return n
}else{
return add8(n,i + 1) + i
}
}
然后变成
function add8 (n,i) {
var i = i || 0;
if (i >= n) {
return n
}
return add8(n,i + 1) + i
}
然后就回到上面的那个递归了
可是从这里怎么变成下面这样的?
function add (n) {
if (n == 0) {
return 0
}
return (n + add(n - 1));
}
这满满的都是很难掌握的东西, 我们就试着体验一下,
要分析 i 和 n 的关系, 从明面上来讲,
i 和 n 似乎没有关系
不存在 i = f(n) ,, 两者没有直接的运算关系.
唯一明显的关系就是, i >=n return n
即, add(n,n) = n
i 的取值范围是 0 ~ n,
存在三个量,
n,i,add()
已知条件
add(n,n) = n
i = 0;
核心关系
add(n,i) = add(n,i + 1) + i
把i 用n 替换一下,
这里的替换方式很明显应该是数学上的运算
我确实不甚了解
或者真的存在这种运算关系吗?
当 i = n 时,
add(n,n) = add(n,n - 1) + n
稍微整理一下就是
function add (n,n) {
if (n == 0) {/此处 i = 0 的初始值变成了 n 的一个边界, 又或者是一个出口
return 0
}
return add(n,n - 1) + n
}
可以看出, (也不怎么好看出),
第一个参数位置的 n 似乎没有也不影响运算
所以最终可以整理出
function add (n) {
if (n == 0) {
return 0
}
return add(n - 1) + n
}
哇塞, 鼓掌.
虽然牵强的部分比较多,
而且可能在专科眼里, 这种程度的数学运算是小儿科.
但我还是给自己鼓一下掌,鼓励一下自己.
从上面,其实我们能够得到很多信息.
- 从大的来讲,
实现同一个功能, 即使用递归实现,
形态可能也是多样的. - 其次, 递归的形态 可以通过 = , return, 的关系
以及变量和变量的关系的整理,
进行转换. - 对比一下累加,迭代方式的最简洁形态和递归的最简洁形态,
可以看出,一般 迭代方式所需要的变量数量, 要比递归形态的数量要多.
比如 按照上面的例子来讲 迭代方式, 似乎必须存在 一个变量sum
sum = sum + n
等式左右两侧的sum 值 明显是不同的,
左边的sum 代表接收返回值, 右边的sum 表示运算中的参数
即, 用 一个sum 完成了前一次和后一次的值传递?
严格来讲应该是这样的
var sum1 = 0;/ 作为参数的前一个sum
var sum2 = 0;/ 作为接收值的sum
for(;n--;){
sum1 = sum2;/
sum2 = sum1 + n;/
}
很明显, 可以把 sum1 和 sum2 合并成一个. 根据等式替换
而在 递归当中, 没有这个sum , 那么这个sum 的概念是如何体现的? 或者由谁来承载的?
答案是 add(n) 和 add(n - 1)
在递归中, add(n) 和add(n - 1), 又或者 add (n - 2)
并非只是代表函数的执行, 而是代表了一个值, 或者概念.
在这道题中 add(n) 就相当于 sum1 , add(n - 1) 代表 sum2
即, 在递归中, 函数的执行状态, 可以当做一个变量.
不同的参数的执行状态, 即可代表不同变量, 或者 这个变量的不同值?
我们再说一次 add(1) 是一个变量, 这个变量即不是 add 也不是 1, 但就是个变量.
就好像
a 是一个变量, b 是一个变量,
a + b 相当于是一个新的变量
我们可以理解为 var add(a,b) = a + b 即, 我们用 add(a,b) 来代表 a + b 这个变量.
把一个简单至极的道理, 讲得这么让人不想看第二遍, 我也是服了自己了.
但我们稍微注意一下就可以发现,
在迭代方式中, sum = sum + 1 时, 我们始终只是占用了一个sum变量
一旦前一个值完成使命, 就会被后一个值覆盖,内存,也就是从空间上来讲,
很节省.
但反观 递归, add(n),add(n - 1),add(n - 2),add(n - 3) 这些相当于都是不同的变量,
在得到执行完成之前, 都会占用空间.
换个正常点的说法就是,
观察上面的递归可以发现, add(n) 只有在 add(n - 1) 返回确定值的时候, 才能执行完成这个函数.
依次递推就是, 直到 add(0) 之前, 所有的函数会嵌套方式处于执行状态,无法完成
我这个概念学得不是很扎实, 网上称之为压栈.
即, 每执行一个函数,会开启一个栈, 这个栈里存着该函数里的变量, 当执行完的时候,
这个栈可能会被释放,
即,开栈会占用内存, 函数执行完会释放栈, 也就是释放内存,释放空间.
压栈就是, 这个函数还没执行完, 在里面有执行了一个函数, 且只有里面的函数执行完的时候,
外面的函数才能执行完,
这句话的意思很明显, 会存在同时开两个栈,里面的栈关闭外面的才能关闭.
想想, 多少次递归, 就会存在同时开多少个栈的情况, 太多栈,占用太多内存,
必然就有可能出现电脑吃不消的情形 .
这也就是为什么, 网上大多数人说, 递归虽然比迭代简单,
但能用迭代替换递归就尽量替换递归的一个原因.
另一个原因是说, 迭代比递归执行效率更高.
可能也是作用域链的问题, 也就是压栈压多了,运行起来是不是会慢一点?
关于这个不是很清楚, 我想知道的也不是这个.
如果你跟我一样是个新手,
你应该会和我有同样的一个疑问.
即,
人说递归比迭代简单, 或者简洁,我怎么时常没这个感觉?
比如上面那个forEach,reduce 的 递归版本, 我就感觉非常的不舒服, 不好阅读, 难以理解.
答案是, 我写得烂呗.
我们不是得出一个结论, 同一个功能递归函数, 可以很复杂, 也可能很简洁嘛.
所以第一个可能的答案是,我写得烂.
但这就相当于是一句废话,我们想要的是递归的优势,
你跟我讲, 你代码写得烂,体会不出, 这不是废话嘛.
我猜测是这样的,
有时候递归的方式, 也就是函数的方式,
能够更好的表达或体现一些概念?
特别是能够体现归纳法的概念?
所以只要我们把一个问题,变成一个从归纳的角度分析的问题,
在用递归翻译, 就会变得很简洁?
比如累加法,中 累加1,100之间的数字.
变成归纳的概念就是, 100 + 1,99的累加
所以,
我们上面完成的例子, 基本都是把迭代 改成 递归,
这个过程当中, 我可能是走了一个比较难的路子,
即, 我想把迭代时,遇到的概念(变量), 原封不动的去改成递归.
可能存在另一种方式,
即, 我可以从整体角度,看这到底干了什么? 想要解决什么问题?
然后从概念上, 变成一个归纳的问题? 然后再翻译成 递归?
当然我只是说说,,呵,,呵
上面都是把迭代改成递归
在我们接触把递归改成 迭代之前,
我们再做几个例子,
如果能够发现一些转换的通式自然是最好,
下面是一个用双重循环写的排序
var arr = [1,5,96,3,88,5,8,5,9];
// 排序, 双重循环
function sort (arr) {
var len = arr.length;
for(var i = 0; i < len - 1; i++) {
for(var j = i + 1; j < len; j++) {
var temp;
if (arr[i] <= arr[j]) {
// 交换数据
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
}
sort(arr);
我们试着改成递归,
我这都还没开始想, 就有点头疼了.
先改成 while
function sort (arr) {
var len = arr.length;
// 首先改成 递减
while (len--){
var j = len
while (j--){
var temp;
if (arr[len] >= arr[j]) {
// 交换数据
temp = arr[j];
arr[j] = arr[len];
arr[len] = temp;
}
}
}
}
再改成, 跟循环没区别的递归版本
function sort (arr) {
var len = arr.length;
// 首先改成 递减
while (len--){
var j = len
while (j--){
var temp;
if (arr[len] >= arr[j]) {
// 交换数据
temp = arr[j];
arr[j] = arr[len];
arr[len] = temp;
}
}
}
}
再把最外层, 给干掉, 所有参数尽量全传进去
function go1 (arr,len) {
var len = len || arr.length;
len--;
function go2 (len,j) {
j--;
var temp;
if (arr[len] >= arr[j]) {
// 交换数据
temp = arr[j];
arr[j] = arr[len];
arr[len] = temp;
}
if (j > 0) {
go2(len,j);
}
}
go2(len,len);
if (len > 0) {
go1(arr,len);
}
}
go1(arr);
然后考虑 变量之间的关系 以及等式替换
搞不下去了.
勉强能够做到把迭代改成递归,
只是目前来讲有两个限定条件,
一个是, 该题中的函数不涉及 返回值
另一个是, 需要先改成 while循环, 以捋清思路.
关于迭代改成递归,就先到这里,
反正日后遇到一些迭代, 我们可以当做一些待做的题, 放到这里来, 试着慢慢改一改.
明天, 我们就学习一下, 怎样把递归改成迭代,
你会发现, 网上基本都是教你怎样把 递归改迭代.
明天再说.
