没有合适的资源?快使用搜索试试~ 我知道了~
这几天恰好和朋友谈起了递归,忽然发现不少朋友对于“尾递归”的概念比较模糊,网上搜索一番也没有发现讲解地完整详细的资料,于是写了这么一篇文章,权当一次互联网资料的补充。:P 递归与尾递归 关于递归操作,相信大家都已经不陌生。简单地说,一个函数直接或间接地调用自身,是为直接或间接递归。例如,我们可以使用递归来计算一个单向链表的长度: 代码如下: public class Node { public Node(int value, Node next) { this.Value = value; this.Next = next; }
资源推荐
资源详情
资源评论
C#中的尾递归与中的尾递归与Continuation详解详解
这几天恰好和朋友谈起了递归,忽然发现不少朋友对于“尾递归”的概念比较模糊,网上搜索一番也没有发现讲解地完整详细的
资料,于是写了这么一篇文章,权当一次互联网资料的补充。:P
递归与尾递归递归与尾递归
关于递归操作,相信大家都已经不陌生。简单地说,一个函数直接或间接地调用自身,是为直接或间接递归。例如,我们可以
使用递归来计算一个单向链表的长度:
代码如下:
public class Node
{
public Node(int value, Node next)
{
this.Value = value;
this.Next = next;
}
public int Value { get; private set; }
public Node Next { get; private set; }
}
编写一个递归的GetLength方法:
代码如下:
public static int GetLengthRecursively(Node head)
{
if (head == null) return 0;
return GetLengthRecursively(head.Next) + 1;
}
在调用时,GetLengthRecursively方法会不断调用自身,直至满足递归出口。对递归有些了解的朋友一定猜得到,如果单项链
表十分长,那么上面这个方法就可能会遇到栈溢出,也就是抛出StackOverflowException。这是由于每个线程在执行代码时,
都会分配一定尺寸的栈空间(Windows系统中为1M),每次方法调用时都会在栈里储存一定信息(如参数、局部变量、返回
地址等等),这些信息再少也会占用一定空间,成千上万个此类空间累积起来,自然就超过线程的栈空间了。不过这个问题并
非无解,我们只需把递归改成如下形式即可(在这篇文章里我们不考虑非递归的解法):
代码如下:
public static int GetLengthTailRecursively(Node head, int acc)
{
if (head == null) return acc;
return GetLengthTailRecursively(head.Next, acc + 1);
}
GetLengthTailRecursively方法多了一个acc参数,acc的为accumulator(累加器)的缩写,它的功能是在递归调用时“积累”之
前调用的结果,并将其传入下一次递归调用中——这就是GetLengthTailRecursively方法与GetLengthRecursively方法相比在
递归方式上最大的区别:GetLengthRecursive方法在递归调用后还需要进行一次“+1”,而GetLengthTailRecursively的递归调
用属于方法的最后一个操作。这就是所谓的“尾递归”。与普通递归相比,由于尾递归的调用处于方法的最后,因此方法之前所
积累下的各种状态对于递归调用结果已经没有任何意义,因此完全可以把本次方法中留在堆栈中的数据完全清除,把空间让给
最后的递归调用。这样的优化1便使得递归不会在调用堆栈上产生堆积,意味着即时是“无限”递归也不会让堆栈溢出。这便是
尾递归的优势。
有些朋友可能已经想到了,尾递归的本质,其实是将递归方法中的需要的“所有状态”通过方法的参数传入下一次调用中。对于
GetLengthTailRecursively方法,我们在调用时需要给出acc参数的初始值:
代码如下:
GetLengthTailRecursively(head, 0)
为了进一步熟悉尾递归的使用方式,我们再用著名的“菲波纳锲”数列作为一个例子。传统的递归方式如下:
代码如下:
public static int FibonacciRecursively(int n)
{
if (n < 2) return n;
return FibonacciRecursively(n – 1) + FibonacciRecursively(n – 2);
}
而改造成尾递归,我们则需要提供两个累加器:
代码如下:
public static int FibonacciTailRecursively(int n, int acc1, int acc2)
{
if (n == 0) return acc1;
return FibonacciTailRecursively(n – 1, acc2, acc1 + acc2);
}
资源评论
weixin_38738830
- 粉丝: 6
- 资源: 920
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 数据库异常处理策略:技术深度解析与代码实践
- the tmux configuration file
- 嵌入式开发入门:从单片机选择到电子硬件设计与软件实现
- 双轴心 同步带模组说明书 与伺服驱动器搭配使用
- BGinfo资源,可固定文字内容并调整文字样式在电脑桌面
- 【java毕业设计】基智能选课系统的设计与实现源码(ssm+mysql+说明文档).zip
- 《基于JavaScript实现校园二手交易平台》+项目源码+文档说明
- 5S07-A2升级视频.rar
- jsp ssm 非物质文化遗产网站 非遗管理网站 项目源码 web java【项目源码+数据库脚本+项目说明+软件工具】毕设
- 雷赛 伺服驱动器STP文件
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功