从最早学C语言的时候接触递归的时候就写过递归函数了。什么从1加到100，算阶乘等等。不过因为递归的函数调用操作要浪费不少时间，加上写起来也没习惯，就不怎么爱用。

最近稍微接触了一点Haskell这种函数式编程语言，然后就又想起C语言的递归了。之后在C语言里也尝试了Haskell里那样的写法。有说“尾递归可以转变为循环”，似乎编译器优化也是这么做的。但是自己在尝试的时候却没发现它变成了循环。

比如这样的一个很简单的算1+2+3+…+n的递归函数，

#include <stdio.h>
int sum(int m)
{
    if(m == 0) return 0;
    else return m + sum(m-1);
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", sum(n));
    return 0;
}

就算加了/Ox参数来编译，最终也还是看到sum里有对sum的调用，出来的代码是这样的

_m$ = 8							; size = 4
_sum	PROC
	push	esi
	mov	esi, DWORD PTR _m$[esp]
	test	esi, esi
	jne	SHORT $LN2@sum
	xor	eax, eax
	pop	esi
	ret	0
$LN2@sum:
	lea	eax, DWORD PTR [esi-1]
	push	eax
	call	_sum
	add	esp, 4
	add	eax, esi
	pop	esi
	ret	0
_sum	ENDP

前一段时间看到一篇博文，专门讲关于尾递归优化的。看得时间有点长了所以在哪里看的记得不是太清楚了。像这样 m + sum(m-1) 的写法，因为算了sum的值以后还要回头来加 m 才行，所以这个m的值就不得不保留，这样在整个递归过程中，每个调用栈帧的m就必须都保留，说到底（扶额

解决方法就是不要弄出这样的写法，m的话先给它加进去就行了，参数弄个变量代表当前结果，代码变成这样

#include <stdio.h>
int sum_internal(int n, int s)
{
    if(n == 0) return s;
    else return sum_internal(n-1, s+n);
}
int sum(int n)
{
    return sum_internal(n, 0);
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", sum(n));
    return 0;
}

这样在递归过程中，没有需要保留的东西了，相当于说就可以直接利用当前栈帧来进行下一次函数调用，于是生成的代码变成

_n$ = 8							; size = 4
_s$ = 12						; size = 4
_sum_internal PROC
	mov	ecx, DWORD PTR _n$[esp-4]
	mov	eax, DWORD PTR _s$[esp-4]
	test	ecx, ecx
	je	SHORT $LN8@sum_intern
	npad	4
$LL5@sum_intern:
	add	eax, ecx
	dec	ecx
	jne	SHORT $LL5@sum_intern
$LN8@sum_intern:
	ret	0
_sum_internal ENDP
_TEXT	ENDS
PUBLIC	_sum

_n$ = 8							; size = 4
_sum	PROC
	mov	eax, DWORD PTR _n$[esp-4]
	test	eax, eax
	jne	SHORT $LN4@sum
	ret	0
$LN4@sum:
	push	eax
	dec	eax
	push	eax
	call	_sum_internal
	add	esp, 8
	ret	0
_sum	ENDP

（其中sum调用sum_internal的部分被展开了一层，所以会先检查参数n是不是0……）

看到函数 sum_internal 里面现在没有call了，这下递归不是递归被转成循环了，于是递归写起来也超放心了，没有函数调用的时间开销也没有栈帧的空间开销。之后大概就会写出像haskell里面那样一大堆递归的代码（殴）。阶乘的话大概是这样

int fact_internal(int n, int f)
{
    if (n == 1) return f;
    else return fact_internal(n-1, f*n);
}
int fact(int n)
{
    return fact_internal(n, 1);
}

（其实如果是C++的话，似乎写一个函数就好了，第二个参数可以给个默认值……

斐波那契数列因为要保存的状态有两个，所以

#include <stdio.h>
int f(int n, int p1, int p2)
{
    if (n == 1 || n == 2) return p1;
    return f(n-1, p1+p2, p1);
}

int main()
{
    int i;
    for(i = 1; i <= 20; ++i)
        printf("%d\t", f(i, 1, 1));
}

写着写着实在有一种“循环过程中用到的局部变量有几个就要几个参数”的那种感觉囧

不过毕竟换汤不换药，到头来可以被优化为循环，也就是说一开始就有办法写成循环？唔……