递归正如‘盗梦空间’中的场景：
PS: 使用《windows用户, 截屏新手段》可以一句for循环生成类似这种效果的图。
简言之就是不断调用自己，
经常我们会拿fibonacci数来讲解递归，正如在Rabbits and Recurrence
Relations一题中所实现的，我使用了静态变量来缓存，以加快运行速度。R版本的实现可以参考tricky things in R一文，相对应于C的静态变量，在R中使用了局部的全局变量，这需要用<<-来赋值。
在开发ggtree时，unrooted layout最早的版本就是使用递归实现，但BiocCheck会把<<-报出来，而Bioconductor的人不喜欢看到这个赋值符，于是我改成了现在的版本，使用for loop。递归和循环一样，都只是程序的一种控制机制，某些递归实现代码非常短的同时，可读性非常强。
Example 1
比如我们要写writeSequence这样的函数：
Call Output
writeSequence(1); 1
writeSequence(2); 1 1
writeSequence(3); 2 1 2
writeSequence(4); 2 1 1 2
writeSequence(5); 3 2 1 2 3
writeSequence(6); 3 2 1 1 2 3
public void writeSequence(int n) {
if (n < 1)
throw new IllegalArgumentException();
if (n == 1) {
System.out.print(1);
return;
}
if (n == 2) {
System.out.print("1 1");
return;
}
int x = (int) Math.ceil(n/2.0);
System.out.print(x + " ");
writeSequence(n-2);
System.out.print(" " + x);
}
先定义跳出递归的base case，然后就是不断调用自己，把结果插在中间。
Example 2
List L Limit n maxSum(L, n) returns
[7, 30, 8, 22, 6, 1, 14] 19 16
[5, 30, 15, 13, 8] 42 41
[30, 15, 20] 40 35
[6, 2, 6, 9, 1] 30 24
[11, 5, 3, 7, 2] 14 14
[10, 20, 30] 7 0
[10, 20, 30] 20 20
[] 10 0
再比如这个例子，数列中各种组合的总数，最大但不超过limit的数。
public int maxSum(List list, int n) {
if (n <= 0 || list.size() == 0)
return 0;
int item = list.get(0);
list.remove(0);
int maximum;
if (n < item) {
maximum = maxSum(list, n);
} else {
int with = item + maxSum(list, n-item);
int without = maxSum(list, n);
maximum = Math.max(with, without);
}
list.add(0, item);
return(maximum);
}
如果元素不超过n，可加可不加，然后递归应用到去掉这个元素的数列中。在调用的结尾，我用了list.add()来把删掉的元素放回去，因为我们并不希望调用此函数之后，数列变为空。
Example 3
假如你在爬台阶，一小步是一个台阶，一大步是两个台阶，那么爬4个台阶有以下5种可能性：
[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2]
实现一个函数waysToClimb(n)，返回爬n个台阶的所有方式。
public void waysToClimb(int n) {
Stack steps = new Stack();
waysToClimb(n, steps);
}
public void waysToClimb(int n, Stack steps) {
if (n <= 0) {
System.out.println(steps);
return;
} else {
steps.push(1); // choose 1
waysToClimb(n-1, steps); // explore
steps.pop(); // un-choose
if (n > 1) {
steps.push(2);
waysToClimb(n-2, steps);
steps.pop();
}
}
}
这里使用了Stack来缓存结果，你可以选择一小步或者一大步来走，使用递归可以非常方便地遍历所有的可能性。