p*****2
发帖数: 21240 | 1 大家能不能给点例子不能转变成尾递归的？我想写写看。谢谢。 |
d**e
发帖数: 6098 | 2 比如 get binary tree height ?
【在 p*****2 的大作中提到】
: 大家能不能给点例子不能转变成尾递归的？我想写写看。谢谢。
|
y****n
发帖数: 743 | 3 C(m,n)
【在 p*****2 的大作中提到】
: 大家能不能给点例子不能转变成尾递归的？我想写写看。谢谢。
|
p*****2
发帖数: 21240 | 4
m*(m-1)*(m-2)...吗？
【在 y****n 的大作中提到】
: C(m,n)
|
p*****2
发帖数: 21240 | 5
这个感觉可以呀。为什么你感觉不行呢？
【在 d**e 的大作中提到】
: 比如 get binary tree height ?
|
p*****2
发帖数: 21240 | 6
尾递归
def getHeight(root:TreeNode):Int={
recursion(0,List(root))
}
def recursion(layer:Int, list:List[TreeNode]):Int= list match{
case Nil=> layer
case _ => recursion(layer+1, process(list))
}
def process(list:List[TreeNode]):List[TreeNode]={
var newlist:List[TreeNode]=Nil
for(node<-list){
if(!node.left.isEmpty) newlist=node.left.get::newlist
if(!node.right.isEmpty) newlist=node.right.get::newlist
}
newlist
}
【在 d**e 的大作中提到】
: 比如 get binary tree height ?
|
d**e
发帖数: 6098 | 7 我理解得比较肤浅，觉得tail recrusion应该是省空间。
不过你这个bfs是tail recursion，我错了。。
【在 p*****2 的大作中提到】
:
: 尾递归
: def getHeight(root:TreeNode):Int={
: recursion(0,List(root))
: }
:
: def recursion(layer:Int, list:List[TreeNode]):Int= list match{
: case Nil=> layer
: case _ => recursion(layer+1, process(list))
: }
|
p*****2
发帖数: 21240 | 8
大牛谦虚了。我也是刚学。看看到底尾递归都能做什么。
【在 d**e 的大作中提到】
: 我理解得比较肤浅，觉得tail recrusion应该是省空间。
: 不过你这个bfs是tail recursion，我错了。。
|
y****n
发帖数: 743 | 9 int C(int m, int n)
{
if ((n == 0) || (n == m))
return 1;
else
return C(m - 1, n) + C(m - 1, n - 1);
}
【在 p*****2 的大作中提到】
:
: 大牛谦虚了。我也是刚学。看看到底尾递归都能做什么。
|
p*****2
发帖数: 21240 | 10
尾递归
def C(m:Int, n:Int):Int={
recursion(m, 0, None)(n)
}
def recursion(m:Int, i:Int, arr:Option[Array[Int]]):Array[Int]= i match{
case _ if i==m+1 => arr.get
case 0 => recursion(m, 1, Option(Array[Int](0)))
case _ => val ret=process(i,arr.get); recursion(m, i+1, Option(ret))
}
def process(i:Int, arr:Array[Int]):Array[Int]={
val ar=new Array[Int](i+1)
ar(0)=1
ar(i)=1
1 until i foreach(j=>ar(j)=arr(j)+arr(j-1))
ar
}
【在 y****n 的大作中提到】
: int C(int m, int n)
: {
: if ((n == 0) || (n == m))
: return 1;
: else
: return C(m - 1, n) + C(m - 1, n - 1);
: }
|
|
|
p*****2
发帖数: 21240 | 11 今天问了scala group的人了，确实所有的recursion都可以转换成尾递归。这个貌似没
什么悬念了。 |
y****n
发帖数: 743 | 12 加一点难度。两个函数相互递归
public static double H(double val, int n)
{
if (n == 0)
return val;
else
{
double left = V(val - 1, n - 1);
double right = V(val + 1, n - 1);
return Math.Sqrt(Math.Abs(left * right));
}
}
public static double V(double val, int n)
{
if (n == 0)
return val;
else
{
double up = H(val * 2, n - 1);
double down = H(val / 2, n - 1);
return Math.Sqrt(Math.Abs(up + down));
}
} |
p*****2
发帖数: 21240 | 13
多谢易山，晚上看看。你是做F＃的吗？
【在 y****n 的大作中提到】
: 加一点难度。两个函数相互递归
: public static double H(double val, int n)
: {
: if (n == 0)
: return val;
: else
: {
: double left = V(val - 1, n - 1);
: double right = V(val + 1, n - 1);
: return Math.Sqrt(Math.Abs(left * right));
|
y****n
发帖数: 743 | 14 我常用C#
【在 p*****2 的大作中提到】
:
: 多谢易山，晚上看看。你是做F＃的吗？
|
p*****2
发帖数: 21240 | 15
那怎么对尾递归这么熟？
【在 y****n 的大作中提到】
: 我常用C#
|
y****n
发帖数: 743 | 16 我对尾递归不熟，以前与一位朋友讨论面试题，谈到过。
那道题是：两个正整数x和y，求x/y的余数。禁用循环和乘除法。
我只知道有尾递归这个东西，可以避免递归层数过多时压栈溢出。
我从来没想过把普通递归改写成尾递归，所以对这个贴子比较感兴趣。
我也很好奇：
是不是所有的递归都可以写成非递归？
是不是所有的递归都可以写成尾递归？
是不是尾递归都可以改写成循环形式？
前面出的那道题纯属探讨，没有刁难的意思。
【在 p*****2 的大作中提到】
:
: 那怎么对尾递归这么熟？
|
p*****2
发帖数: 21240 | 17
我个人感觉应该可以。所以想多练习练习。我也是刚接触这东西。正好一起探讨
【在 y****n 的大作中提到】
: 我对尾递归不熟，以前与一位朋友讨论面试题，谈到过。
: 那道题是：两个正整数x和y，求x/y的余数。禁用循环和乘除法。
: 我只知道有尾递归这个东西，可以避免递归层数过多时压栈溢出。
: 我从来没想过把普通递归改写成尾递归，所以对这个贴子比较感兴趣。
: 我也很好奇：
: 是不是所有的递归都可以写成非递归？
: 是不是所有的递归都可以写成尾递归？
: 是不是尾递归都可以改写成循环形式？
: 前面出的那道题纯属探讨，没有刁难的意思。
|
p*****2
发帖数: 21240 | 18
尾递归的实现，不过Scala不支持这种递归的优化。
def H(value:Double, n:Int):Double={
H_helper(Array(value),n)(0)
}
def V(value:Double, n:Int):Double={
V_helper(Array(value),n)(0)
}
def H_helper(arr:Array[Double], n:Int):Array[Double]=n match{
case 0 => caclV(arr)
case _ => {
val ar=new Array[Double](arr.length*2)
for(i<- 0 until arr.length) {
ar(2*i)=arr(i)-1
ar(2*i+1)=arr(i)+1
}
V_helper(ar, n-1)
}
}
def V_helper(arr:Array[Double], n:Int):Array[Double]=n match{
case 0 => caclH(arr)
case _ =>{
val ar=new Array[Double](arr.length*2)
for(i<- 0 until arr.length){
ar(2*i)=arr(i)*2
ar(2*i+1)=arr(i)/2
}
H_helper(ar, n-1)
}
}
def caclH(arr:Array[Double]):Array[Double]={
if(arr.length==1) return arr
val ar=new Array[Double](arr.length/2)
for(i<- 0 until ar.length){
ar(i)=math.sqrt((arr(2*i)*arr(2*i+1)).abs)
}
caclV(ar)
}
def caclV(arr:Array[Double]):Array[Double]={
if(arr.length==1) return arr
val ar=new Array[Double](arr.length/2)
for(i<- 0 until ar.length){
ar(i)=math.sqrt((arr(2*i)+arr(2*i+1)).abs)
}
caclH(ar)
}
【在 y****n 的大作中提到】
: 加一点难度。两个函数相互递归
: public static double H(double val, int n)
: {
: if (n == 0)
: return val;
: else
: {
: double left = V(val - 1, n - 1);
: double right = V(val + 1, n - 1);
: return Math.Sqrt(Math.Abs(left * right));
|
y****n
发帖数: 743 | 19 你太牛了！你这是要逼着我学Scala呀！
【在 p*****2 的大作中提到】
:
: 尾递归的实现，不过Scala不支持这种递归的优化。
: def H(value:Double, n:Int):Double={
: H_helper(Array(value),n)(0)
: }
:
: def V(value:Double, n:Int):Double={
: V_helper(Array(value),n)(0)
: }
:
|
p*****2
发帖数: 21240 | 20
好呀。一起学习呀。今天准备总结一下尾递归，大牛帮助点评一下。
【在 y****n 的大作中提到】
: 你太牛了！你这是要逼着我学Scala呀！
|
|
|
y****n
发帖数: 743 | 21 我试图理解了一下你改写的C(m,n)
有个几问题：
1. 我所理解的尾递归是指在不改变算法的前提下，在函数的结尾处作递归调用。这样
优化编译后，代码可以在进入递归调用之前释放当前函数的堆栈数据。
改编的代码已经修改了算法，计算了很多多余的数据。
比如：C(10,0)，原来直接返回1，改编代码会计算C(0,0)-C(10,n)全部数据
2. 原来代码在最深层调用时，对堆栈的占用是O(m)
而改编的代码对内存的占用是O(m^2)，这样尾递归的意义就不大了。
3. 感觉上改变后的代码已经不需要递归了，循环貌似更简洁。
【在 p*****2 的大作中提到】
:
: 好呀。一起学习呀。今天准备总结一下尾递归，大牛帮助点评一下。
|
p*****2
发帖数: 21240 | |
b*****o
发帖数: 715 | 23 硬币找零问题（100用1，5，10，25有几种表示方法）能不能写成尾递归？
我只能想出用普通递归或者memoization的办法。
【在 p*****2 的大作中提到】
: 总结了一下尾递归
: http://blog.sina.com.cn/s/blog_b9285de20101i5s1.html
|
p*****2
发帖数: 21240 | 24
miss掉的大牛的回复。感觉你的理解稍微有点问题。我是这样理解的。
1. 尾递归的本质就是循环
2. 纯FP是没有循环的，所以才需要尾递归。如果有循环的话，确实没必要这么搞。
【在 y****n 的大作中提到】
: 我试图理解了一下你改写的C(m,n)
: 有个几问题：
: 1. 我所理解的尾递归是指在不改变算法的前提下，在函数的结尾处作递归调用。这样
: 优化编译后，代码可以在进入递归调用之前释放当前函数的堆栈数据。
: 改编的代码已经修改了算法，计算了很多多余的数据。
: 比如：C(10,0)，原来直接返回1，改编代码会计算C(0,0)-C(10,n)全部数据
: 2. 原来代码在最深层调用时，对堆栈的占用是O(m)
: 而改编的代码对内存的占用是O(m^2)，这样尾递归的意义就不大了。
: 3. 感觉上改变后的代码已经不需要递归了，循环貌似更简洁。
|
p*****2
发帖数: 21240 | 25
这个应该比yishan那个容易很多。memoization与尾递归并不矛盾吧？
【在 b*****o 的大作中提到】
: 硬币找零问题（100用1，5，10，25有几种表示方法）能不能写成尾递归？
: 我只能想出用普通递归或者memoization的办法。
|
b*****o
发帖数: 715 | 26 那可能我对尾递归的理解有误。我的理解是，尾递归的state space不会随着问题规模
的增长而增长。
换句话说，不会因为问题规模的变大而出现overflow。
就以硬币问题为例子，普通递归最终会出现stack overflow。而memoization的table最
终也会overflow。但是，真正的尾递归应该不会出现这种问题。难道不是这样吗？
【在 p*****2 的大作中提到】
:
: 这个应该比yishan那个容易很多。memoization与尾递归并不矛盾吧？
|
