t****a
发帖数: 1212 | 1 我不会把任意的递归问题转换成尾递归。比如，
1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
自变量为一维的问题。
2. 程序依赖多个子递归问题，应该怎么办？
3. 多个子函数相互嵌套递归怎么办？
如果有解决这方面问题的尾递归的材料，请分享给我，非常感谢。
我只会用memorize function。效率跟iteration还是差一大截。 |
n******n
发帖数: 567 | 2 为什么不写在global var上面？？tail call和global效率不一样？ |
d**e
发帖数: 6098 | 3 可以把123各举个例子吗？
应该也不是所有递归都可以转化为尾递归的，比如树的遍历就好像不行
【在 t****a 的大作中提到】
: 我不会把任意的递归问题转换成尾递归。比如，
: 1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
: 自变量为一维的问题。
: 2. 程序依赖多个子递归问题，应该怎么办？
: 3. 多个子函数相互嵌套递归怎么办？
: 如果有解决这方面问题的尾递归的材料，请分享给我，非常感谢。
: 我只会用memorize function。效率跟iteration还是差一大截。
|
y*******g
发帖数: 6599 | 4 有些就是不能转
不过你确定memorize比iteration差一大截？ 举个例子？
【在 t****a 的大作中提到】
: 我不会把任意的递归问题转换成尾递归。比如，
: 1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
: 自变量为一维的问题。
: 2. 程序依赖多个子递归问题，应该怎么办？
: 3. 多个子函数相互嵌套递归怎么办？
: 如果有解决这方面问题的尾递归的材料，请分享给我，非常感谢。
: 我只会用memorize function。效率跟iteration还是差一大截。
|
t****a
发帖数: 1212 | 5 分成3类也不见得合适，见谅
例子1, f = function(x, y, z) 其中 x y z为三个参数，如果动态规划表格来表示的
话，就需要存储range(x)*range(y)*range(z)三维
例子2，f(x) = g(f(x-1), f(x-2), ..., f(1)) 其中g是某个依赖于1..x-1的运算，比
如找前面中间最小的之类
例子3, f(x) = f(x-1) + g(x); g(x) = g(x-1) + f(x-1)
【在 d**e 的大作中提到】
: 可以把123各举个例子吗？
: 应该也不是所有递归都可以转化为尾递归的，比如树的遍历就好像不行
|
t****a
发帖数: 1212 | 6 memorize仍然是递归，递归就需要将push pop局部变量，这应该是变慢的重要原因吧。
另外memorize有stackoverflow的风险。JVM上似乎1W层就挂了。
由于会记住所有的调用，memroize还会吃掉大量的内存，可能造成out of memory。迭
代的方法可以自己选择保留什么变量所以没有这个问题。
【在 y*******g 的大作中提到】
: 有些就是不能转
: 不过你确定memorize比iteration差一大截？ 举个例子？
|
t****a
发帖数: 1212 | 7 不懂。这是回答这个问题吗？是什么意思？
【在 n******n 的大作中提到】
: 为什么不写在global var上面？？tail call和global效率不一样？
|
p*****2
发帖数: 21240 | |
n******n
发帖数: 567 | 9 tail call的优势来自于把结果保存在函数的input里面。但如果保存在global变量里面
，不也一样么？这些global存在heap里面，不会每次都recursion 的时候都push pop
【在 t****a 的大作中提到】
: 不懂。这是回答这个问题吗？是什么意思？
|
d**e
发帖数: 6098 | 10 ....这是作业的证明题？
【在 t****a 的大作中提到】
: 分成3类也不见得合适，见谅
: 例子1, f = function(x, y, z) 其中 x y z为三个参数，如果动态规划表格来表示的
: 话，就需要存储range(x)*range(y)*range(z)三维
: 例子2，f(x) = g(f(x-1), f(x-2), ..., f(1)) 其中g是某个依赖于1..x-1的运算，比
: 如找前面中间最小的之类
: 例子3, f(x) = f(x-1) + g(x); g(x) = g(x-1) + f(x-1)
|
|
|
d**e
发帖数: 6098 | 11 你说的有理
但跟他想问的有点不对口
【在 n******n 的大作中提到】
: tail call的优势来自于把结果保存在函数的input里面。但如果保存在global变量里面
: ，不也一样么？这些global存在heap里面，不会每次都recursion 的时候都push pop
|
y*******g
发帖数: 6599 | 12 用指针的话没什么区别吧
【在 n******n 的大作中提到】
: tail call的优势来自于把结果保存在函数的input里面。但如果保存在global变量里面
: ，不也一样么？这些global存在heap里面，不会每次都recursion 的时候都push pop
|
n******n
发帖数: 567 | 13 lz在一楼提到了三种方法: tail call, memorization, iteration(典型DP解法？)
我不明白LZ的问题，你是说想执着的‘放弃典型DP的方法’来找一种方法专门把‘任何
递归化成尾递归’？那这种方法即使存在，尾递归在stack上面的操作也不可能比典型
DP解法更优。那么这么做的唯一原因就是写成尾递归编码更方便（memorization如果想
优化所用到的比tail call多用的内存，还是可以替代掉）。但对于f(x) = g(f(x-1),.
..,f(1))，和多函数互相调用的情况，好像能否存在转化成tail call要和g的具体函数
有关？还是对于2和3这种情况根本就转化不了？但不论怎么样，在代码方面也看不出比
典型DP解法简单。。。。 |
t****a
发帖数: 1212 | 14 个人有点执着的喜欢递归而不是iteration，尾递归像递归却本质上是iteration。谢谢
回复，长知识，这就转包子给你。
,.
【在 n******n 的大作中提到】
: lz在一楼提到了三种方法: tail call, memorization, iteration(典型DP解法？)
: 我不明白LZ的问题，你是说想执着的‘放弃典型DP的方法’来找一种方法专门把‘任何
: 递归化成尾递归’？那这种方法即使存在，尾递归在stack上面的操作也不可能比典型
: DP解法更优。那么这么做的唯一原因就是写成尾递归编码更方便（memorization如果想
: 优化所用到的比tail call多用的内存，还是可以替代掉）。但对于f(x) = g(f(x-1),.
: ..,f(1))，和多函数互相调用的情况，好像能否存在转化成tail call要和g的具体函数
: 有关？还是对于2和3这种情况根本就转化不了？但不论怎么样，在代码方面也看不出比
: 典型DP解法简单。。。。
|
w*******2
发帖数: 8 | 15 尾递归和普通递归的区别就是其栈的空间大小是不随着函数的调用而增长的，所以不会
有stack overflow的问题，通过将所需信息直接通过参数传进调用的子函数，这样的过
程很迭代其实没什么区别，对于一些语言，编译器就直接会把尾递归转化成迭代.
对于简单的递归转化成尾递归，可以通过传递参数的方法来保存之前的状态，但是对于
一些多次调用递归，简单的增加传入参数就不行了，可以使用continuation-passing
style(CPS)来实现，此方法仅适用在函数式编程
就执行效率来说，memorization并不迭代差（不考虑空间复杂度的话）
【在 t****a 的大作中提到】
: 个人有点执着的喜欢递归而不是iteration，尾递归像递归却本质上是iteration。谢谢
: 回复，长知识，这就转包子给你。
:
: ,.
|
t****a
发帖数: 1212 | |
D**********d
发帖数: 849 | 17 例三不是可以直接计算吗:
[1 -1;0 1] [f; g]_x = [1 0; 1 1] [f; g]_{x-1}
==>
[f; g]_x = [1 1;0 1] [1 0; 1 1] [f; g]_{x-1} = [2 1; 1 1] [f; g]_{x-1}
= ... = [2 1; 1 1]^n [f; g]_{0}
而 [2 1; 1 1]^n 可以通过分解用特征值求解 |
t****a
发帖数: 1212 | 18 我不会把任意的递归问题转换成尾递归。比如，
1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
自变量为一维的问题。
2. 程序依赖多个子递归问题，应该怎么办？
3. 多个子函数相互嵌套递归怎么办？
如果有解决这方面问题的尾递归的材料，请分享给我，非常感谢。
我只会用memorize function。效率跟iteration还是差一大截。 |
n******n
发帖数: 567 | 19 为什么不写在global var上面？？tail call和global效率不一样？ |
d**e
发帖数: 6098 | 20 可以把123各举个例子吗？
应该也不是所有递归都可以转化为尾递归的，比如树的遍历就好像不行
【在 t****a 的大作中提到】
: 我不会把任意的递归问题转换成尾递归。比如，
: 1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
: 自变量为一维的问题。
: 2. 程序依赖多个子递归问题，应该怎么办？
: 3. 多个子函数相互嵌套递归怎么办？
: 如果有解决这方面问题的尾递归的材料，请分享给我，非常感谢。
: 我只会用memorize function。效率跟iteration还是差一大截。
|
|
|
y*******g
发帖数: 6599 | 21 有些就是不能转
不过你确定memorize比iteration差一大截？ 举个例子？
【在 t****a 的大作中提到】
: 我不会把任意的递归问题转换成尾递归。比如，
: 1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
: 自变量为一维的问题。
: 2. 程序依赖多个子递归问题，应该怎么办？
: 3. 多个子函数相互嵌套递归怎么办？
: 如果有解决这方面问题的尾递归的材料，请分享给我，非常感谢。
: 我只会用memorize function。效率跟iteration还是差一大截。
|
t****a
发帖数: 1212 | 22 分成3类也不见得合适，见谅
例子1, f = function(x, y, z) 其中 x y z为三个参数，如果动态规划表格来表示的
话，就需要存储range(x)*range(y)*range(z)三维
例子2，f(x) = g(f(x-1), f(x-2), ..., f(1)) 其中g是某个依赖于1..x-1的运算，比
如找前面中间最小的之类
例子3, f(x) = f(x-1) + g(x); g(x) = g(x-1) + f(x-1)
【在 d**e 的大作中提到】
: 可以把123各举个例子吗？
: 应该也不是所有递归都可以转化为尾递归的，比如树的遍历就好像不行
|
t****a
发帖数: 1212 | 23 memorize仍然是递归，递归就需要将push pop局部变量，这应该是变慢的重要原因吧。
另外memorize有stackoverflow的风险。JVM上似乎1W层就挂了。
由于会记住所有的调用，memroize还会吃掉大量的内存，可能造成out of memory。迭
代的方法可以自己选择保留什么变量所以没有这个问题。
【在 y*******g 的大作中提到】
: 有些就是不能转
: 不过你确定memorize比iteration差一大截？ 举个例子？
|
t****a
发帖数: 1212 | 24 不懂。这是回答这个问题吗？是什么意思？
【在 n******n 的大作中提到】
: 为什么不写在global var上面？？tail call和global效率不一样？
|
p*****2
发帖数: 21240 | |
n******n
发帖数: 567 | 26 tail call的优势来自于把结果保存在函数的input里面。但如果保存在global变量里面
，不也一样么？这些global存在heap里面，不会每次都recursion 的时候都push pop
【在 t****a 的大作中提到】
: 不懂。这是回答这个问题吗？是什么意思？
|
d**e
发帖数: 6098 | 27 ....这是作业的证明题？
【在 t****a 的大作中提到】
: 分成3类也不见得合适，见谅
: 例子1, f = function(x, y, z) 其中 x y z为三个参数，如果动态规划表格来表示的
: 话，就需要存储range(x)*range(y)*range(z)三维
: 例子2，f(x) = g(f(x-1), f(x-2), ..., f(1)) 其中g是某个依赖于1..x-1的运算，比
: 如找前面中间最小的之类
: 例子3, f(x) = f(x-1) + g(x); g(x) = g(x-1) + f(x-1)
|
d**e
发帖数: 6098 | 28 你说的有理
但跟他想问的有点不对口
【在 n******n 的大作中提到】
: tail call的优势来自于把结果保存在函数的input里面。但如果保存在global变量里面
: ，不也一样么？这些global存在heap里面，不会每次都recursion 的时候都push pop
|
y*******g
发帖数: 6599 | 29 用指针的话没什么区别吧
【在 n******n 的大作中提到】
: tail call的优势来自于把结果保存在函数的input里面。但如果保存在global变量里面
: ，不也一样么？这些global存在heap里面，不会每次都recursion 的时候都push pop
|
n******n
发帖数: 567 | 30 lz在一楼提到了三种方法: tail call, memorization, iteration(典型DP解法？)
我不明白LZ的问题，你是说想执着的‘放弃典型DP的方法’来找一种方法专门把‘任何
递归化成尾递归’？那这种方法即使存在，尾递归在stack上面的操作也不可能比典型
DP解法更优。那么这么做的唯一原因就是写成尾递归编码更方便（memorization如果想
优化所用到的比tail call多用的内存，还是可以替代掉）。但对于f(x) = g(f(x-1),.
..,f(1))，和多函数互相调用的情况，好像能否存在转化成tail call要和g的具体函数
有关？还是对于2和3这种情况根本就转化不了？但不论怎么样，在代码方面也看不出比
典型DP解法简单。。。。 |
|
|
t****a
发帖数: 1212 | 31 个人有点执着的喜欢递归而不是iteration，尾递归像递归却本质上是iteration。谢谢
回复，长知识，这就转包子给你。
,.
【在 n******n 的大作中提到】
: lz在一楼提到了三种方法: tail call, memorization, iteration(典型DP解法？)
: 我不明白LZ的问题，你是说想执着的‘放弃典型DP的方法’来找一种方法专门把‘任何
: 递归化成尾递归’？那这种方法即使存在，尾递归在stack上面的操作也不可能比典型
: DP解法更优。那么这么做的唯一原因就是写成尾递归编码更方便（memorization如果想
: 优化所用到的比tail call多用的内存，还是可以替代掉）。但对于f(x) = g(f(x-1),.
: ..,f(1))，和多函数互相调用的情况，好像能否存在转化成tail call要和g的具体函数
: 有关？还是对于2和3这种情况根本就转化不了？但不论怎么样，在代码方面也看不出比
: 典型DP解法简单。。。。
|
w*******2
发帖数: 8 | 32 尾递归和普通递归的区别就是其栈的空间大小是不随着函数的调用而增长的，所以不会
有stack overflow的问题，通过将所需信息直接通过参数传进调用的子函数，这样的过
程很迭代其实没什么区别，对于一些语言，编译器就直接会把尾递归转化成迭代.
对于简单的递归转化成尾递归，可以通过传递参数的方法来保存之前的状态，但是对于
一些多次调用递归，简单的增加传入参数就不行了，可以使用continuation-passing
style(CPS)来实现，此方法仅适用在函数式编程
就执行效率来说，memorization并不迭代差（不考虑空间复杂度的话）
【在 t****a 的大作中提到】
: 个人有点执着的喜欢递归而不是iteration，尾递归像递归却本质上是iteration。谢谢
: 回复，长知识，这就转包子给你。
:
: ,.
|
t****a
发帖数: 1212 | |
D**********d
发帖数: 849 | 34 例三不是可以直接计算吗:
[1 -1;0 1] [f; g]_x = [1 0; 1 1] [f; g]_{x-1}
==>
[f; g]_x = [1 1;0 1] [1 0; 1 1] [f; g]_{x-1} = [2 1; 1 1] [f; g]_{x-1}
= ... = [2 1; 1 1]^n [f; g]_{0}
而 [2 1; 1 1]^n 可以通过分解用特征值求解 |
p*****2
发帖数: 21240 | 35
这不是违反FP的理念了吗？
【在 n******n 的大作中提到】
: tail call的优势来自于把结果保存在函数的input里面。但如果保存在global变量里面
: ，不也一样么？这些global存在heap里面，不会每次都recursion 的时候都push pop
|
p*****2
发帖数: 21240 | 36
感觉树的遍历应该可以
【在 d**e 的大作中提到】
: 可以把123各举个例子吗？
: 应该也不是所有递归都可以转化为尾递归的，比如树的遍历就好像不行
|
p*****2
发帖数: 21240 | 37
我最近也在思考这个问题。
【在 t****a 的大作中提到】
: 我不会把任意的递归问题转换成尾递归。比如，
: 1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
: 自变量为一维的问题。
: 2. 程序依赖多个子递归问题，应该怎么办？
: 3. 多个子函数相互嵌套递归怎么办？
: 如果有解决这方面问题的尾递归的材料，请分享给我，非常感谢。
: 我只会用memorize function。效率跟iteration还是差一大截。
|
p*****2
发帖数: 21240 | 38 1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
自变量为一维的问题。
感觉这个可以解决呀。 |
p*****2
发帖数: 21240 | 39
,.
典型DP利用了mutable变量，这个和FP的理念不符。
【在 n******n 的大作中提到】
: lz在一楼提到了三种方法: tail call, memorization, iteration(典型DP解法？)
: 我不明白LZ的问题，你是说想执着的‘放弃典型DP的方法’来找一种方法专门把‘任何
: 递归化成尾递归’？那这种方法即使存在，尾递归在stack上面的操作也不可能比典型
: DP解法更优。那么这么做的唯一原因就是写成尾递归编码更方便（memorization如果想
: 优化所用到的比tail call多用的内存，还是可以替代掉）。但对于f(x) = g(f(x-1),.
: ..,f(1))，和多函数互相调用的情况，好像能否存在转化成tail call要和g的具体函数
: 有关？还是对于2和3这种情况根本就转化不了？但不论怎么样，在代码方面也看不出比
: 典型DP解法简单。。。。
|
l*******b
发帖数: 2586 | 40 嗯，functional里面的lazy evaluation sequence不知道怎么实现的．这个和
memorization有点像吧，像fibonacci数列那样的．不知道是bottom up的实现还是top
down的实现，bottom up貌似不需要stack 调用，top down就是递归了，当然这个例子
两个是等价的可以互相转化，可以写成尾递归的形式．一般的就不知道了．看看那位大
牛讲讲
【在 p*****2 的大作中提到】
:
: ,.
: 典型DP利用了mutable变量，这个和FP的理念不符。
|
|
|
p*****2
发帖数: 21240 | 41
top
我刚写了一个尾递归，解决2维dp，你帮我看看。
http://www.mitbbs.com/article_t/JobHunting/32313551.html
【在 l*******b 的大作中提到】
: 嗯，functional里面的lazy evaluation sequence不知道怎么实现的．这个和
: memorization有点像吧，像fibonacci数列那样的．不知道是bottom up的实现还是top
: down的实现，bottom up貌似不需要stack 调用，top down就是递归了，当然这个例子
: 两个是等价的可以互相转化，可以写成尾递归的形式．一般的就不知道了．看看那位大
: 牛讲讲
|
