免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: OwnWaterloo

[算法][C]二叉搜索树的两路二分查找 [复制链接]

论坛徽章:
0
发表于 2012-08-09 21:42 |显示全部楼层
本帖最后由 hbmhalley 于 2012-08-09 21:43 编辑

回复 97# OwnWaterloo


    其实,你所谓的递归也仅仅是个挂着递归牌子的冒牌尾递归,并没有把问题分解 各自解决,而是简单地缩小问题的范围,这直接导致你和他说的是一回事。可又明明不是一回事,为什么呢?因为顶楼的问题太 tm 蛋疼了。说他是递归,冒牌的。说他满足某个不变式,这个不变式又几乎占了算法的全部,怎么实现一看便知,不值得讨论。

    如果拿一个需要分解的问题说事,那么是不适合用循环不变式的。
    如果要说明一个步骤复杂的算法,那么循环不变式才有优势,而像递归一样 单凭参数就能说明几乎所有问题的方法,就显得太简陋。

    总之,不是一个东西,不值得讨论。为毛能讨论起来呢?因为顶楼的问题太 tm 蛋疼了

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-09 21:49 |显示全部楼层
回复 101# hbmhalley

分解?我怎么觉得你说的不是递归而是分治?
递归居然还分冒牌与正牌的?正牌递归是怎样的递归?


确实蛋疼,不过你可以去事情起因(2楼有链接)看看。
看看什么叫没有最蛋疼,只有更蛋疼。
看看是不是怎么实现一看便知、不值得讨论。

论坛徽章:
0
发表于 2012-08-09 22:05 |显示全部楼层
本帖最后由 hbmhalley 于 2012-08-09 22:08 编辑

回复 102# OwnWaterloo


    就是划成若干子问题,缩写“分解”。递归与分治也不矛盾。这不重要。
    冒牌的意思就是,递归是把自己分裂成若干子问题,而你把自己“分裂”成一个子问题,实际上就是蜕了层皮,减了减肥,并没体现“分解问题”的作用。
    正牌递归,就是非递归不可的递归,当然你也可以挂个栈 声称是“冒牌不递归”,不过没啥意义。例子不举了,各种非暴力不可的npc问题应有尽有

    我去 .. 原问题明明比二分还要裸,根据二叉搜索树的定义,整棵树简直是在描述(黄金?)分的步骤。顺着往下走不就好了 .. 最多沿路记几个备用的答案

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-09 22:33 |显示全部楼层
回复 103# hbmhalley

也就是说:

  1. int factorial(int n) { return n<2? 1: n*factorial(n-1); }
复制代码
是递归而

  1. int factorial(int n, int p=1) { return n<2? p: factorial(n-1, n*p); }
复制代码
不是递归?

或者,再来个"分叉"的:

  1. int fibonacci(int n) { return n<2? n: fibonacci(n-1) + fibonacci(n-2); }
复制代码
是递归而

  1. int fibonacci(int n, int a=0, int b=1) { return n==0? a: fibonacci(n-1, b, a+b); }
复制代码
不是递归?

又或者那种始终没法转换为在常数空间内下达到线性的 —— 比如二叉树中序遍历 —— 才叫递归?


hbmhalley 发表于 2012-08-09 22:05
冒牌的意思就是,递归是把自己分裂成若干子问题,而你把自己“分裂”成一个子问题,实际上就是蜕了层皮,减了减肥,并没体现“分解问题”的作用。
正牌递归,就是非递归不可的递归,

好奇问问,对递归的这种定义是出自哪里?

hbmhalley 发表于 2012-08-09 22:05
就是划成若干子问题,缩写“分解”。递归与分治也不矛盾。这不重要。

我觉得很重要,因为我对递归这个词的理解里,没有包含必须分解为多个子问题。所以一听冒牌递归,简直吓尿了。
递归的这种定义,出处应该不需要我找吧?纯函数式语言虽不是主流,但也不少。按你的说法,他们天天都在用的那个就是冒牌的了。
或者就在前面几个回帖里就有一个定义,sicp称其为linear recursive process。


@starwing83,你看这是不是functional与imperative的区别。。。

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-09 22:50 |显示全部楼层
回复 103# hbmhalley

>> 我去 .. 原问题明明比二分还要裸,根据二叉搜索树的定义,整棵树简直是在描述二(黄金?)分的步骤。顺着往下走不就好了 .. 最多沿路记几个备用的答案

你现在就可以google一下,看看有多少人写二分搜索,但其实是将区间划分为左中右并且如果中与key相等就退出的?
只要中间元素与key相等就退出是不可能找到边界的。


至于沿路记备用答案
你将代码理解为二分+在沿路记答案。
我将代码理解为二分+特殊的区间划分方式。
对同一事物的看待方式/理解/视角不同而已。


就像你根据是否能转换为循环将递归划分为伪递归与真递归。

而对于我,既然递归可以描述循环可以做的事,也可以描述循环不能做的事(你所谓的真递归),还要循环这个概念干嘛?
于是只有原本就是线性的递归与原本就不是线性的递归。
虽说不是所有语言都保证能优化尾调用,但原本就是线性的递归手工转换为循环并不是难事。 反而是在有些语言里就是没法写循环(包括C++的TMP)。
【至于将递归与分治的概念混淆的事,暂且不表。】

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-09 22:55 |显示全部楼层
回复 103# hbmhalley

关于看待同一事物的不同角度,再给你举个例,就是前面的:

  1. int factorial(int n, int p=1) { return n<2? p: factorial(n-1, n*p); }
复制代码
可以理解这是为了达成尾递归优化。
也可以理解为这是求解一个不同的问题 f(n,p) = p*n!。 于是 g(n) =  n! = f(n,1)。

论坛徽章:
5
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:1115-16赛季CBA联赛之新疆
日期:2024-02-21 10:00:53
发表于 2012-08-09 23:28 |显示全部楼层
呵呵同学这话的确汗……

我只看,不说话……

论坛徽章:
0
发表于 2012-08-09 23:31 |显示全部楼层
回复 106# OwnWaterloo


    啊这都不重要,其实某楼重点不在冒牌与否,而是后一句:“这直接导致你和他说的是一回事”。意思就是要想说递归比单纯依赖循环不变式强在哪,光是没能力的尾递归是说明不了什么的,你懂得,不解释了。能说明问题的是什么呢,是正牌递归,你也懂得。

   
而对于我,既然递归可以描述循环可以做的事,也可以描述循环不能做的事(你所谓的真递归),还要循环这个概念干嘛?

    至于这个,我也提过,“冒牌不递归”当然是有的。就是说,不存在只有一方能做的事。两者其实是等价的,但用栈描述一个实际上是递归的算法,是罪恶的;反过来,用尾递归描述一个清晰的循环(当然那个fac(n)什么的无可厚非莫蛋疼,我指有点规模的算法)也是不光彩的。
    而各自所擅长,或者说,正常的工作领域,在上面某楼,拿二分或者疑似二分说事是绝b毛也说不清楚的。

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-09 23:34 |显示全部楼层
回复 107# starwing83

说嘛,把我勾起吐槽OO一大堆就想自己抽身?

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-09 23:49 |显示全部楼层
回复 108# hbmhalley

>> 意思就是要想说递归比单纯依赖循环不变式强在哪,光是没能力的尾递归是说明不了什么的,你懂得,不解释了。
没说要强在哪啊?但也没弱在哪吧?本来就是一回事,我倾向用递归描述而已。


>> 能说明问题的是什么呢,是正牌递归,你也懂得。
就像你说的,本楼这问题对此是无力的。


>> 但用栈描述一个实际上是递归的算法,是罪恶的;
这里的递归你指的是真递归而非伪递归?

>> 反过来,用尾递归描述一个清晰的循环(当然那个fac(n)什么的无可厚非莫蛋疼,我指有点规模的算法)也是不光彩的。

有些语言函数嵌套调用是有限制的 —— 比如C语言。用栈实现(而非你说的描述)一个实际上是递归的算法即使是罪恶的,有时候也不得不做。
有些语言支持尾调用优化,并且也许用来支持函数调用链的那个东西的上限只受到物理内存的限制。也就是说自己使用栈或者直接用调用链作为栈都一样。这样就可以让程序员不做这些罪恶的事情。

而还有些语言是尽可能将有副作用的代码隔离的。用尾递归去实现也没什么不光彩的。因为绕过副作用的隔离会更不光彩。


这是说实现。而描述的话,前者确实很罪恶,而后者没觉得有什么不光彩。
有可能不会直接用递归描述,而换用map/fold之类由递归实现的处理range的。总之,循环在functional里真的很难被想到。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP