C语言的递归问题 为什么会倒过来执行一次

首先先跟你说下，你是不是忘了你的递归函数，首尾都要输出。注意程序缩进，养成好习惯。

void up_and_down(int n)
{
	printf("Level %d: n location %p\n",n,&n);
	if(n<4)
		up_and_down(n+1);
	printf("LEVEL %d: n location %p\n",n,&n);
}

以你的例子而言，首先是展开过程（此时n<4），在调用递归函数前先要执行第一行的输出语句，然后调用递归语句up_and_down(1+1);进入下一层函数，依次类推，你看到了1、2、3、4。当n=4时展开阶段结束，不再调用递归函数，但仍要依照顺序执行此函数全部语句，所以要输出4，函数执行完毕后，要返回函数调用处（up_and_down(3+1);的下一句），继续按顺序执行输出语句printf("LEVEL %d: n location %p\n",n,&n); 输出3，同理再依次输出2、1

所以最后看到的是1 2 3 4 4 3 2 1

up_and_down(1); 
    printf("1");
    up_and_down(1+1); 
        printf("2");
        up_and_down(2+1); 
            printf("3");
            up_and_down(3+1); 
                printf("4");
                printf("4");
            printf("3");
        printf("2");
    printf("1");

递归解决问题本来就是先展开，直到遇到终止条件，然后再逐层返回，并不是算到最后一层，就直接返回给第一层调用处。以阶乘为例：

Rescuvie(5)
{5 * Rescuvie(4)}
{5 * {4 * Rescuvie(3)}}
{5 * {4 * {3 * Rescuvie(2)}}}
{5 * {4 * {3 * {2 * Rescuvie(1)}}}}
{5 * {4 * {3 * {2 * 1}}}}
{5 * {4 * {3 * 2}}}
{5 * {4 * 6}}
{5 * 24}
120

由于递归的这种特性，所以要占据很大的空间，如果一直没有遇到递归终止条件，则会一直进行下去，直到资源耗尽。阶乘数大于某一程度，计算机就无法解决了。

因此与迭代相比递归是十分低效的算法，不过由于递归有抽象的表达能力，只要有递推关系，不必求出具体表达式就可以求解问题，所以应用还是比较广泛的。

以上方法都被称为线性递归，也可以说是传统的递归。而你后面说的尾递归，是另一种新的方法，与传统的线性递归相比，可节省资源所占资源，避免资源耗尽的问题。

下面举阶乘尾递归的例子

long TailRescuvie(long n, long a) {
    return(n == 1) ? a : TailRescuvie(n - 1, a * n);
}
long TailRescuvie(long n) {//封装用的
    return(n == 0) ? 1 : TailRescuvie(n, 1);
}

TailRescuvie(5)
TailRescuvie(5, 1)
TailRescuvie(4, 5)
TailRescuvie(3, 20)
TailRescuvie(2, 60)
TailRescuvie(1, 120)
1-2返回120
2-3返回120
3-4返回120
4-5返回120
TailRescuvie(5，1)返回120给TailRescuvie(5)
返回并输出120

很容易看出，普通的线性递归比尾递归更加消耗资源，在实现上说，每次重复的过程调用都使得调用链条不断加长，系统不得不使用栈进行数据保存和恢复。而尾递归就不存在这样的问题，因为他的状态完全由n和a保存。

就思想而言，尾递归其实也是一种线性递归，不过它把运算结果（或路径）传给了下一层，编译器可以利用这一特点对语句进行优化，节省所占资源。而且当遇到终止条件后，虽然形式上仍要返回，但计算已经结束，只要将值不断返回即可，不必再运算，因此每次分配的内存不会因为递归而扩大。

尾递归适用于运算对当前递归路径有依赖的问题，传统递归适用于运算对更深层递归有依赖的问题。从效率来看两者都差不多，不过编译器对尾递归可以进行优化，大大减小尾递归所占资源，而普通递归，编译器的优化没太大影响。（如果都不优化，其实所占资源差不多）

如果你改写下long TailRescuvie(long n, long a);使得它在头尾输出n（递归调用前后都输出），你会发现输出结果仍然是，n、n-1 ……2 1 1 2……n-1、n的过程。

不存在你说的到一半就结束了。

long TailRescuvie(long n, long a) {
	cout<<n<<endl;
	long b;
	if(n==1)
	{
		cout<<n<<endl;
		return a ;
	}
	else
		b=TailRescuvie(n - 1, a * n);
	cout<<n<<endl;
	return b ;
}

“函数执行完毕后，要返回函数调用处（up_and_down(3+1);的下一句）”
看到这就看不懂了。。能加个百度HI吗？

main()
{
……
fun(a,b);
a=a+1;
cout<<a;
}

up_and_down(1); //调用up_and_down(1);
    printf("1");
    up_and_down(1+1); //调用up_and_down(1+1);
        printf("2");
        up_and_down(2+1); //调用up_and_down(2+1);
            printf("3");
            up_and_down(3+1); //调用up_and_down(3+1);
                printf("4");
                printf("4");  //执行完毕，返回up_and_down(3+1);执行它的下一句
            printf("3");//执行完毕，返回up_and_down(2+1);执行它的下一句
        printf("2");//执行完毕，返回up_and_down(1+1);执行它的下一句
    printf("1");