NOVELL She Calves Puzzle

iIf a cow produces its first she-calf at age two years and after that
produces another single she-calf every year, how many she-calves are
there after 12 years? assuming none die.

My Answer

A algorithm to enumerate all the combinations of given numbers

/*
A algorithm to enumerate all the combinations of given numbers
Author : Anders Ma [2011_0419]
*/
#include

int array[100];
int cursor = 0;

void enumerate(int n)
{
int i;

for(i = 0; i < cursor; ++i)
printf("%d,", array[i]);
if (cursor != 0)
printf("\n");

for (i = 0; i < n; ++i) {
array[cursor++] = i + 1;
enumerate(i);
cursor--;
}
}

int
main(int argc, char **argv)
{
enumerate(5);
return 0;
}

anders@ubuntu:~/c$ ./enum
1,
2,
2,1,
3,
3,1,
3,2,
3,2,1,
4,
4,1,
4,2,
4,2,1,
4,3,
4,3,1,
4,3,2,
4,3,2,1,
5,
5,1,
5,2,
5,2,1,
5,3,
5,3,1,
5,3,2,
5,3,2,1,
5,4,
5,4,1,
5,4,2,
5,4,2,1,
5,4,3,
5,4,3,1,
5,4,3,2,
5,4,3,2,1,

递归调用背后的玄机

在函数调用前，首先要将被调用函数所需要的参数放入堆栈。然后执行汇编指令CALL进行函数调用，与此同时CALL下面一条指令的地址也压入到了堆栈中。当函数返回时，调用RET指令。RET指令会从堆栈中取出一个地址（CALL压入的地址），之后程序从这个地址继续向下执行。这样调用完函数还可以按照既定顺序去执行。

函数调用是A调用B，递归调用则是A调用A。递归调用和函数调用在堆栈的处理方式上是有区别的，只是我们平时不会用汇编去玩递归，很多堆栈操作都被Compiler代工。

下面是一段使用递归调用的C函数代码：
0001: void
0002: merge_sort(int array[], int p, int r)
0003: {
0004: int q;
0005:
0006: if (r > p) {
0007: q = (p + r) / 2;
0008: merge_sort(array, p, q);
0009: merge_sort(array, q + 1, r);
000a: merge(array, p, q, r);
000b: }
000c: }

反汇编(objdump -d)后函数代码如下：

0001 <merge_sort>:
0001: push %ebp
0002: mov %esp,%ebp
0003: sub $0x28,%esp
0004: mov 0x10(%ebp),%eax
0005: cmp 0xc(%ebp),%eax
0006: jle 8048691 <merge_sort+0x7f>
0007: mov 0x10(%ebp),%eax
0008: mov 0xc(%ebp),%edx
0009: lea (%edx,%eax,1),%eax
000a: mov %eax,%edx
000b: shr $0x1f,%edx
000c: lea (%edx,%eax,1),%eax
000d: sar %eax
000e: mov %eax,-0xc(%ebp)
000f: mov -0xc(%ebp),%eax
0010: mov %eax,-0x10(%ebp)
0011: mov -0xc(%ebp),%eax
0012: mov %eax,0x8(%esp)
0013: mov 0xc(%ebp),%eax
0014: mov %eax,0x4(%esp)
0015: mov 0x8(%ebp),%eax
0016: mov %eax,(%esp)
0017: call 8048612 <merge_sort>
0018: mov -0xc(%ebp),%eax
0019: lea 0x1(%eax),%edx
001a: mov 0x10(%ebp),%eax
001b: mov %eax,0x8(%esp)
001c: mov %edx,0x4(%esp)
001d: mov 0x8(%ebp),%eax
001e: mov %eax,(%esp)
001f: call 8048612 <merge_sort>
0020: mov 0x10(%ebp),%eax
0021: mov %eax,0xc(%esp)
0022: mov -0xc(%ebp),%eax
0023: mov %eax,0x8(%esp)
0024: mov 0xc(%ebp),%eax
0025: mov %eax,0x4(%esp)
0026: mov 0x8(%ebp),%eax
0027: mov %eax,(%esp)
0028: call 8048414 <merge>
0029: leave
002a: ret

分析：
1 C[0008]对应A[0017],可以看出A[000e~0016]是把参数array，p，q
压入堆栈，这和普通的函数调用相同。所以很显然，在 r > p 的情况下， C[0008]的持续执行，会导致堆栈中有很多组 array, p,
q，r变量。
2 C[0009]对应A[001f],C[0009]什么时候调用？答：C[0008]引起的调用违反条件(r >
p)后，C[0009]会被执行。A[0018~001e]在做什么？嗯，这就是递归调用的特殊一面，如果是正常函数调用，是不需要这段代码的。那到底A[0018~001e]在做什么？就是把堆栈里面之前保存的一组参数提取出来，然后再讲这组参数压入堆栈，为C[0009]调用做准备。你可能会想拿出来在放进去这不是瞎折腾吗？非也！我们从C代码角度看，提取步骤让局部变量（array，p，q，r）的值已经变成之前堆栈保存的那组数据了，这是重点。之后再把局部变量放入堆栈这是为了后续函数调用做准备。
3 C[000a]对应A[0028]，C[000ａ]什么时候调用？答：道理同上。A[0020~0027]在做什么？道理同上，哈哈。
4 对A程序的疑惑，为什么上来只有push，没有看到pop？其实leave就完成了这个动作，请看注释2。

总结：
递归调用需要在汇编语言级别做特殊处理。对于特殊处理，直白点讲，就是把最后吃进去的给我吐出来。吐到哪里？吐到局部变量里。这样变量就来了一次超级大变身!!!

注释1：C[000a] 代表 C语言000a行；A[000a] 代表汇编语言000a行；
注释2：LEAVE : Set SP to BP, then pop BP.

How to become a world-class programmer

If you want to be a good programmer, you just program ever day for two
years, you will be an excellent programmer. If you want to be a
world-class programmer, you can program every day for ten years, or
you can program every day for two years and take an algorithms class.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/