我从尾调优化问题中获得了动力什么是尾部调用优化？
所以,我决定看看如何在平原C中做到这一点.
所以,我编写了2个阶乘程序,第1个可以应用尾部调用优化.我把这个事实函数称为事实(n,1).
unsigned long long int fact(int n, int cont)
{
if(n == 0)
return cont;
else return fact(n-1, n * cont);
}
2nd是需要多个堆栈帧的正常递归.
unsigned long long int fact(int n)
{
if(n == 0)
return 1;
else return n * fact(n-1);
}
这是由32位编译器为前者生成的-02组件
0x8048470 <fact>: push %ebp
0x8048471 <fact+1>: mov %esp,%ebp
0x8048473 <fact+3>: mov 0x8(%ebp),%edx
0x8048476 <fact+6>: mov 0xc(%ebp),%eax
0x8048479 <fact+9>: test %edx,%edx
0x804847b <fact+11>: je 0x8048488 <fact+24>
0x804847d <fact+13>: lea 0x0(%esi),%esi
0x8048480 <fact+16>: imul %edx,%eax
0x8048483 <fact+19>: …c compiler-construction gcc compiler-optimization tail-call-optimization
无限递归通常是不希望的,当它发生时通常会导致堆栈溢出或段错误.
但是出于理论的缘故和普通的好奇心,我一直在想是否有可能有意识地创造实际的无限递归.
在C++和C中工作,其中堆栈通常为每个函数调用增长,并且每个函数返回并弹出它处理的堆栈部分.
这是想法.是否可以强制函数清除它自己的堆栈空间然后调用另一个函数,以便新函数有效地替换第一个函数,而第一个函数不需要返回,然后通过循环再次触发.
我不只是考虑将普通循环作为一种可能的用途,如果有的话.循环通常可以很好地完成他们的工作.但是,如果您使用它通过节点网络发送信号,那么它会在自己的进程线程中无限期地继续运行,直到它们达到某个条件.它可能是一个可用于解决某些问题的工具.
记住,我不是在问它是否实用,只有在可能的情况下.对于科学!
这是我测试的代码:
#include <iostream>
#include <chrono>
using namespace std;
#define CHRONO_NOW chrono::high_resolution_clock::now()
#define CHRONO_DURATION(first,last) chrono::duration_cast<chrono::duration<double>>(last-first).count()
int fib(int n) {
if (n<2) return n;
return fib(n-1) + fib(n-2);
}
int main() {
auto t0 = CHRONO_NOW;
cout << fib(45) << endl;
cout << CHRONO_DURATION(t0, CHRONO_NOW) << endl;
return 0;
}
当然,有更快的方法来计算斐波纳契数,但这是一个很好的小压力测试,专注于递归函数调用.除了使用计时器测量时间之外,代码没有别的了.
首先,我在OS X上的Xcode中运行了几次测试(这样就是铿锵声),使用-O3优化.跑了大约9秒钟.
然后,我在Ubuntu上使用gcc(g ++)编译了相同的代码(再次使用-O3),该版本只用了大约6.3秒就可以运行了!此外,我在我的Mac上运行VirtualBox内部的 Ubuntu ,这只会对性能产生负面影响,如果有的话.
你去吧:
在OS X上克服 - > ~9秒
在VirtualBox中的 Ubuntu 上的 gcc - > ~6.3秒.
我知道这些是完全不同的编译器,所以他们做的事情不同,但我看到的所有gcc和clang的测试只显示出更少的差异,在某些情况下,差异是另一种方式(clang更快) ).
因此,在这个特定的例子中,为什么gcc能够以英里数击败？
我在这里找到了以下问题:
如果数组列表太大,以下递归代码将导致堆栈溢出.你如何解决这个问题仍然保留递归模式？
答案是:
通过修改nextListItem函数可以避免潜在的堆栈溢出,如下所示:
var list = readHugeList();
var nextListItem = function() {
var item = list.pop();
if (item) {
// process the list item...
setTimeout( nextListItem, 0);
}
};
由于事件循环处理递归而不是调用堆栈,因此消除了堆栈溢出.当nextListItem运行时,如果item不为null,则将超时函数(nextListItem)推送到事件队列并退出函数,从而使调用堆栈保持清零.当事件队列运行其超时事件时,将处理下一个项目并设置计时器以再次调用nextListItem.因此,在没有直接递归调用的情况下从开始到结束处理该方法,因此无论迭代次数如何,调用栈都保持清晰.
有人可以向我解释一下:
我需要优化代码以获得一些新代码的空间.我没有所有变化的空间.我不能使用代码库切换(80c31与64k).
我对 Erlang 还很陌生，并试图解决无法更改变量的问题。假设我创建了一个堆栈并想要添加一个新元素。如果我无法为列表分配新值，我将如何更新堆栈？我每次都需要创建一个新列表吗？
例如，我在想 Push 可能看起来像
List = [X|List].
然后流行音乐将是
[Head|Tail] = List
Head
List = Tail
当然，这是行不通的，因为我无法更改 List 的值，这就是我的问题。任何帮助表示赞赏。
下午好，我希望这里的人可以帮助我了解我所缺少的东西。我自由地承认这是一项家庭作业，但是我们被允许在代码上进行协作，因此希望这里有人愿意帮忙。
对于此程序，我需要使用递归和迭代来旋转C ++中的三个项目。我的递归案例没有任何问题，但迭代版本给我带来了很多麻烦。我尝试过的所有操作都会产生段错误或无限打印。这是代码，再次感谢您的帮助：
template<typename A, typename B, typename C>
class Triple{
public:
A first;
B second;
C third;
Triple(A a, B b, C c){ first = a; second = b; third = c;}
A fst(){return first;}
B snd(){return second;}
C thd(){return third;}
// The function change1(), changes the first component of a triple.
void change1(A a){ first = a;}
};
// A linked list of triples where the order of the triple rotates as it goes.
template<typename A, typename B, …我似乎不理解这段代码的输出:
function fib(x) {
return (x === 0 || x === 1) ? x : fib(x - 1) + fib(x - 2);
}
fib(7);
// output is 13
这是我的思考过程:
该函数如何得到13的结果？
在获取Linkedlist中的节点数的这两个实现中,时间复杂度是否会发生变化？
private int getCountIterative() {
Node start = head;
int count = 0;
while (start != null)
{
count++;
start = start.next;
}
return count;
}
private int getCountRecursive(Node node) {
if (node == null)
return 0;
return 1 + getCountRecursive(node.next);
}
我有一个清单 ['','','',['',[['a','b']['c']]],[[['a','b'],['c']]],[[['d']]]]
我想用索引展平列表，输出应如下所示：
flat list=['','','','','a','b','c','a','b','c','d']
indices=[0,1,2,3,3,3,3,4,4,4,5]
这该怎么做？
我已经试过了：
def flat(nums):
res = []
index = []
for i in range(len(nums)):
if isinstance(nums[i], list):
res.extend(nums[i])
index.extend([i]*len(nums[i]))
else:
res.append(nums[i])
index.append(i)
return res,index
但这不能按预期工作。