过程式语言中的尾调用

在scheme中,尾调用完全是循环的:

(define factor
  (lambda (n result)
    (if (< n 2)
      result
      (factor (- n 1) (* result n)))))

这段代码和

int factor(int n){
  int result = 1;
  while(n >= 2) {
    result = n * result;
    n--;
  }
  return result;
}

具有完全相同的时间和空间复杂度。这是由于scheme中使用的不是【栈】,而是【继续】(continuation)。如果读者不知道什么是【继续】,可以继续关注我的博客,我会写另外一篇文章来专门解释这个问题。

但在c语言那样的语言中,类似于上面的scheme的代码会产生多余的栈增长:

int rec_factor(int n, int ret) {
	if (n < 2) {
		return ret;
	}
	else {
		return rec_factor(n - 1, ret * n);
	}
}

这是因为,在调用rec_factor(n - 1, ret * n)时,这个rec_factor(n, ret)的局部变量、参数等等,都是没有用的。换言之,它应该【退出】之后再调用rec_factor()

【蹦床】技术

为了解决这个问题,编程语言专家们引入了【蹦床】技术。这个技术的核心是【先退出,再调用】,如果你把【退出函数】想象成落下,【调用函数】想象成弹起,那么C语言的尾调用就是【跳跳跳跳跳。。。落落落落落】,而再使用了蹦床技术之后,尾调用就像是【跳落跳落跳落。。。】,自然就像一个【蹦床】一样了。

怎么实现呢?我们再考察一下刚才的函数:

int rec_factor(int n, int ret) {
	if (n < 2) {
		return ret;
	}
	else {
		return rec_factor(n - 1, ret * n);
	}
}

如果return的不是一个【函数调用】,而是一个【值】,那么,它就会在这里直接返回。而我们可以在外部用这个【值】来继续计算rec_factor(n - 1, ret * n),或者说,调用rec_factor(n - 1, ret * n)。

我们先改写一下:

Bounce rec_factor(int n, int ret) {
	if (n < 2) {
		return Bounce;
	}
	else {
		return Bounce;
	}
}

可见,这个Bounce需要既能包住一个【值】(也就是C中的值),又能包住一个【调用】。怎么设计呢?如果使用C++的话,我们有lambda()[]{},std::function之类的匿名函数可以做到【包住调用】这点,但我们这里不用这些东西,而是使用自己定义的数据结构:

struct Bounce {
	typedef Bounce (*func)(void*, void*);
	func f;
	void* args;
	void* return_value;
	bool end;
};

这里的func类型是为了方便而定义的,第一个参数是【参数的指针】,第二个参数是【返回值的指针】,而它在语法意义上的返回值则是一个Bounce。end用来区分它是一个【函数调用】还是一个【值】。

由于bounce包含了【要调用的函数指针、参数】,它自然可以用来保存调用。我们来看一下改写后的factor函数:

Bounce factor(int * n, int* ret) {
	if (*n < 2) {
		Bounce b;
		b.return_value = ret;
		b.end = true;
		return b;
	}
	else {
		*ret = (*n) * (*ret);
		*n = (*n) - 1;
		Bounce b;
		b.f = (Bounce::func)factor;
		b.args = n;
		b.return_value = ret;
		b.end = false;
		return b;
	}
}

自然,这样的【函数】是不能直接调用的,因为它返回一个Bounce,我们需要另一个函数来**不断地处理bounce,直至得到一个【被包住的值】,而不是【被包住的调用】为止:

void* Tramp(Bounce b) {
	if (b.end == true)
	{
		return b.return_value;
	}
	else {
		auto hot = b;
		while (!hot.end)
		{
			hot = hot.f(hot.args, hot.return_value);
		}
		return b.return_value;
	}
}

在外部,我们会这样来调用它:


int main()
{
	Bounce b;
	b.f = (Bounce::func)factor;
	b.args = malloc(4);
	*(int*)b.args = 100000;
	b.return_value = malloc(4);
	*(int*)(b.return_value) = 1;
	b.end = false;
	Tramp(b);
// 	rec_factor(100000, 1);
	std::cout << *(int*)b.return_value << std::endl;
}

下面那行被注释掉的代码,会爆栈;而我们用【蹦床】技术写的等效代码,则不会爆栈。这样一来,对于所有的尾调用,只要调用的函数满足func类型的函数声明,都可以这样调用而不会消耗额外的栈空间。