递归正如‘盗梦空间’中的场景：

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来缓存结果，你可以选择一小步或者一大步来走，使用递归可以非常方便地遍历所有的可能性。