C#函数式编程中的递归调用之尾递归详解

关于递归相信大家已经熟悉的不能再熟悉了，所以笔者在这里就不多费口舌，不懂的读者们可以在博客园中找到很多与之相关的博客。下面我们直接切入正题，开始介绍尾递归。

尾递归

普通递归和尾递归如果仅仅只是从代码的角度出发来看，我们可能发现不了他的特点，所以笔者利用两张堆栈上的图来展示具体的差距在哪，首先我们来看看普通的递归调用的情况，如下图1.1所示：

假设这里执行的函数是Func1，并且Func1中通过递归调用了自己，那么我们可以看到栈上在每次调用Func1的时候都会重新将函数返回地址等其他参数放入栈中，在递归次数较少的情况下，这样是不会有问题的。但如果递归调用次数达到一定的数量级，则会将栈空间消耗光。因此，就提出了尾递归。而尾递归的栈图如1.2所示：

一样还是递归，但是每次执行自身的时候并不会在栈空间中申请新的空间，类似于for循环的效果，面对递归次数很多的情况下也不会出现什么问题。但是新的问题就出来了，在C#中编译器不会做到这一步优化，而是在jit编译器执行时才会进行优化。并且只有64位才进行优化。在语言的层面上我们也要遵守一定的原则，才能让编译器知道去优化。当然有些喜欢看博客的人可能早就知道尾递归就是在最后return的时候调用自身。我们可以通过一串示意代码来看尾调用：

代码如下:

int Func1()
{
  return Func1();
}

当然上面这串代码会形成一个死循环，因为这里我们没有基线条件。下面我们举一个例子：

这个函数想必应该会比较熟悉，就是计算阶乘的。但是我们可以发现函数sunfc最后的返回语句并不是直接调用函数本身，而是x*sfunc(x -1)，恰恰就是因为前面这个x*就会导致编译器无法优化，从而只能采用普通的递归调用的方式去执行，那么我们就需要利用一些模式去改变，首先我们先介绍的是“累加器传递模式”，可能名字比较悬乎，其实就是将当前的计算结果传递给下一次调用函数中，这样当到达基线条件后直接根据上次计算的结果算出最终结果返回即可，如果将上面的代码采用这个模式就是下面这个样子：

采用这个模式之后我们就变回了尾递归了，当执行到基线条件时，直接返回y的值即可。根本不需要回溯到以前。除了利用这种模式，我们还可以利用一种“后继传递模式”，跟累加器传递模式一样也需要修改函数签名，增加一个参数，我们继续修改上面这串代码：

相比累加器传递模式，这种方式比较难理解，其实sfunc在到达基线条件时y就等同于下面这个lambda表达式：a => a*4*3*2，然后就是调用y(1)就直接计算最终的结果了。在简单点就是y这个函数被包装了了好几层，比如上面这段函数执行结束时y的调用顺序：

a为1传递给y(2 * a)，结果就是y(2)。

a为2传递给y(3 * a)，结果就是y(6)。

a为6传递给y(4 * a)，结果就是y(24)。

a为24传递给x => x，输出24。

如果还是不理解只能下断点，调试自己琢磨琢磨了，实在不懂的可以Q问。

在满足必要的经济的条件下,研究更加高深的技术.满足自己的野心

赞 (0)

相关推荐

  • C#函数式编程中的递归调用之尾递归详解

    C#函数式编程中的递归调用之尾递归详解

    关于递归相信大家已经熟悉的不能再熟悉了,所以笔者在这里就不多费口舌,不懂的读者们可以在博客园中找到很多与之相关的博客.下面我们直接切入正题,开始介绍尾递归. 尾递归 普通递归和尾递归如果仅仅只是从代码的角度出发来看,我们可能发现不了他的特点,所以笔者利用两张堆栈上的图来展示具体的差距在哪,首先我们来看看普通的递归调用的情况,如下图1.1所示: 假设这里执行的函数是Func1,并且Func1中通过递归调用了自己,那么我们可以看到栈上在每次调用Func1的时候都会重新将函数返回地址等其他参数放入栈中

  • Java编程中的4种代码块详解

    在Java编程中,代码块就是指用"{}"括起来的代码.下面看一下这四种代码块. 1.普通代码块 就是指类中方法的方法体. public void xxx(){ //code } 2.构造块 下面用"{}"括起来的代码片段,构造块在创建对象时会被调用,每次创建对象时都会被调用,并且优先于类构造函数(包括有参和无参的)执行. 构造块中定义的变量是局部变量. public class Client { {//构造代码块 System.out.println("执

  • C#面向对象编程中里氏替换原则的示例详解

    目录 里氏替换原则 C# 示例 糟糕的示范 正确的示范 总结 在面向对象编程中,SOLID 是五个设计原则的首字母缩写,旨在使软件设计更易于理解.灵活和可维护.这些原则是由美国软件工程师和讲师罗伯特·C·马丁(Robert Cecil Martin)提出的许多原则的子集,在他2000年的论文<设计原则与设计模式>中首次提出. SOLID 原则包含: S:单一功能原则(single-responsibility principle) O:开闭原则(open-closed principle) L

  • 对vue中methods互相调用的方法详解

    如下所示: 最近在学习vue,并用vue+vue-router+axios+elementUI做了一个pos收银系统的前端页面,但是中间遇到methods里的方法调用问题.本身源码是没有调用的,但是我想直接调用多方便,结果出错了--然后百度了一波,终于解决了~ 分享并做个笔记. delAllOrderList:function(goods) { this.tableData = []; this.totalCount = 0; this.money = 0; }, checkout:functi

  • java中构造器内部调用构造器实例详解

    可能为一个类写了多个构造器,有时可能想在一个构造器里面调用另外一个构造器,为了减少代码的重复,可用this关键字做到这一点. public class Flower { private String string; private int age; public Flower() { // 先调用public Flower(String string, int age) this("leon", 120); // 先调用public Flower(String string, int

  • Python编程中*args与**kwargs区别作用详解

    相信学Python的小伙伴肯定有这样的尴尬局面,给一个函数不会用, 原因是:不知道参数列表中的类型是什么意思,比如初学者都会疑问的:*args和**kwargs到底是怎么用. 当你知道这个时,我猜你肯定能会用好多函数了! #*args的用法:当传入的参数个数未知,且不需要知道参数名称时. def func_arg(farg, *args): print("formal arg:", farg) for arg in args: print("another arg:"

  • C#面向对象编程中接口隔离原则的示例详解

    目录 接口隔离原则 C# 示例 糟糕的示范 正确的示范 总结 在面向对象编程中,SOLID 是五个设计原则的首字母缩写,旨在使软件设计更易于理解.灵活和可维护.这些原则是由美国软件工程师和讲师罗伯特·C·马丁(Robert Cecil Martin)提出的许多原则的子集,在他2000年的论文<设计原则与设计模式>中首次提出. SOLID 原则包含: S:单一功能原则(single-responsibility principle) O:开闭原则(open-closed principle) L

  • C#面向对象编程中开闭原则的示例详解

    目录 开闭原则 C# 示例 改进 总结 在面向对象编程中,SOLID 是五个设计原则的首字母缩写,旨在使软件设计更易于理解.灵活和可维护.这些原则是由美国软件工程师和讲师罗伯特·C·马丁(Robert Cecil Martin)提出的许多原则的子集,在他2000年的论文<设计原则与设计模式>中首次提出. SOLID 原则包含: S:单一功能原则(single-responsibility principle) O:开闭原则(open-closed principle) L:里氏替换原则(Lis

  • C#面向对象编程中依赖反转原则的示例详解

    C#面向对象编程中依赖反转原则的示例详解

    在面向对象编程中,SOLID 是五个设计原则的首字母缩写,旨在使软件设计更易于理解.灵活和可维护.这些原则是由美国软件工程师和讲师罗伯特·C·马丁(Robert Cecil Martin)提出的许多原则的子集,在他2000年的论文<设计原则与设计模式>中首次提出. SOLID 原则包含: S:单一功能原则(single-responsibility principle) O:开闭原则(open-closed principle) L:里氏替换原则(Liskov substitution pri

  • Python函数式编程指南（四）：生成器详解

    4. 生成器(generator) 4.1. 生成器简介 首先请确信,生成器就是一种迭代器.生成器拥有next方法并且行为与迭代器完全相同,这意味着生成器也可以用于Python的for循环中.另外,对于生成器的特殊语法支持使得编写一个生成器比自定义一个常规的迭代器要简单不少,所以生成器也是最常用到的特性之一. 从Python 2.5开始,[PEP 342:通过增强生成器实现协同程序]的实现为生成器加入了更多的特性,这意味着生成器还可以完成更多的工作.这部分我们会在稍后的部分介绍. 4.2. 生成

随机推荐