从基础概念解释“伪”递归

  1. 云栖社区>
  2. 博客>
  3. 正文

从基础概念解释“伪”递归

长征6号 2016-09-05 14:11:00 浏览400
展开阅读全文

起因 老赵 使用Lambda表达式编写递归函数

经过 鹤冲天 反驳老赵之“伪”递归

结果 James.Ying 驳“反驳老赵之“伪”递归”

 

摘要:老赵提了个“伪”递归的说法

=========================

Func<int, int> fac = null;
fac = x => x <= 1 ? 1 : x * fac(x - 1);
Console.WriteLine(fac(5)); // 120;

Func<int, int> facAlias = fac;
fac = x => x;
Console.WriteLine(facAlias(5)); // 20

  第一次打印出的120是正确的结果。不过facAlias从fac那里“接过”了使用Lambda表达式构造的委托对象之后,我们让fac引用指向了新的匿名方法x => x。于是facAlias在调用时:

facAlias(5)     <— facAlias是x => x <= 1 ? 1 : x * fac(x – 1)
= 5 <= 1 ? 1 : 5 * fac(5 - 1)
= 5 * fac(4)    <— 注意此时fac是x => x
= 5 * 4
= 20

  自然就不对了。

=============================

老赵其实解释得也很清楚:

这个Lambda表达式构造的“委托对象”在调用时,它会去寻找fac这个引用所指向的委托对象。请注意,这里是根据“引用”去找“对象”,这意味着Lambda表达式构造的委托对象在调用时,fac可能已经不再指向当初的委托对象了。

 

我理解的意思就是老赵说facAlias的定义虽然看起来很像递归,但是本质上不是递归,所以一时兴起起个名字叫“伪”递归

结果人家鹤冲天不干了,觉得老赵对于Lambda递归有偏见。

================================== 

先说下老赵这篇文章的由来,我之前也写过一篇和递归有关的随笔《由Fibonacci数列引出“委托扩展”及“递推递归委托”》,里面给出了这样的一个递归定义(以下称为代码一):

public static Func<int, int> Fibonacci = n => n > 1 ? Fibonacci(n - 1) + Fibonacci(n - 2) : n;

是计算Fibonacci数列的,注意上这句代码中用了“static”,可以编译通过,绝对没有问题!老赵回复中说不用static无法编译通过,于是我又给出了以下代码(以下称为代码二):

    Func<int, int> Fibonacci = null;
    Fibonacci = n => n > 1 ? Fibonacci(n - 1) + Fibonacci(n - 2) : n;

代码二就是老赵随笔中开始处的那两行被称为“伪”递归代码,所说的朋友自然就是我了!

===================================

呵呵,人家老赵没说代码二是伪递归呀。facAlies才是呢。并且老赵的希望不是仅仅构造一个递归,而是希望

我的想法是,既然使用“Lambda表达式来构造一个递归函数”的难点是因为“我们正在构造的东西是没有名字的”,因此“我们无法调用自身”。那么,如果我们换种写法,把我们正在调用的匿名函数作为参数传给自己,那么不就可以在匿名函数的方法体中,通过调用参数来调用自身了吗?

以及从这个出发点开始扩展下去的东西

不过结果是James.Ying对鹤冲天进行了一些使用IL的探究,不过问题出在这么一个表达上

这样我们能清楚些,当我们执行委托的时候,会使用Invoke(args)来调用方法体,看清楚,是Invoke方法,并不是委托自己哦,这一点已经偏离了递归的概念了。

这是个原则性问题,我的跟帖也就是冲这个去的

其实很多问题根本不需要IL来凑热闹。

最后,使用最基础的内存堆栈结构概念来解释老赵的代码

回顾基本概念,值类型、引用类型。

Func<int, int> fac = null;

fac = x => x <= 1 ? 1 : x * fac(x - 1);

Func<int, int> facAlias = fac;

fac = x => x;

Console.WriteLine(facAlias(5)); // 20

第一行,在内存中的情况如下

image

第二行

image

 

第三行

image

第四行

image

第五行的运行结果自然就是老赵说的:

facAlias(5) <— facAlias是x => x <= 1 ? 1 : x * fac(x – 1)

= 5 <= 1 ? 1 : 5 * fac(5 - 1)

= 5 * fac(4) <— 注意此时fac是x => x

= 5 * 4

= 20

所以facAlias不是一个递归Lambda表达式,因此可以认为是一种“伪递归”

Func<int, int> fac = null;

fac = x => x <= 1 ? 1 : x * fac(x - 1);

这里的fac是一个如假包换的递归

=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+

最后谢谢各位观赏

作者:徐少侠
出处:http://www.cnblogs.com/Chinese-xu/

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接。
如有问题,可以通过 Chinese_Xu@126.com 联系我,非常感谢。

分享家:Addthis中文版
标签: 伪递归, lambda

本文转自徐少侠博客园博客,原文链接:http://www.cnblogs.com/Chinese-xu/archive/2009/09/02/1558547.html,如需转载请自行联系原作者

网友评论

登录后评论
0/500
评论
长征6号
+ 关注