Question

5. 设有一个递归算法如下 int x (int n) { if (n<=3) return 1; else return x(n-2)+x(n-4)+1; }

试问计算 x(x(8))时需要计算（ ）次x函数。求大神解答！

Answer 1

18次，调用需要9次；x（9）调用乱昌9次，加在一起共18次。

递归函数在调用自身后直接传回其值，而不对其再加运算。尾部递归与循环是等价的，而且在一些语言可以被优化为循环指令。 因此，在这些语言中尾部递归不会占用调用堆栈空间。

既然在这里函数不能调用其自身，我们可以用 Z 组合子应用这个函数后得到的函数再应用需计算的参数。

扩展资料：

数据类型可以通过递归来进行定义，比如一个简单的递归定义为自然数的定义：“一个自然数或等于0，或等于另一个自然数加上1”。

这一定义相当于宣告“一个链表或是空串列，或是一个御陪败链表镇颤之前加上一个字符串”。可以看出所有链表都可以通过这一递归定义来达到。

Answer 2

18次——因为x(8)==9，它需要调用9次；x(9)也要调用9次，共18次。

Answer 3

#include<stdio.h>
#include<malloc.h>

int 改慧count = 0;
int x 兆悄(int n)
{
	count = count + 1;
	printf("%d  n = %d\n", count, n);
	if 族歼渣(n<=3)
	{
		return 1;
	}
	else
	{
		return x(n-2)+x(n-4)+1;
	}
}

int main(void)
{
	x(x(8));
	return 0;
}