问题

在一个村庄里有i个人，他们每个人只能寄出一封信，接收一封信，并且不能给自己寄信。那么请问一共有多少种寄信收信方式。

思路

遇到此类问题，应该从简单的情况考虑。比如，当村里只有两个人的时候，只有一种寄信方法；如果有两个人的时候，A,B,C，A可以寄信给B或者C，这两种情况下剩余的人没有别的寄信方法，所以只有两种方法；当有四个人的时候，我们假设A把一封信给了B，此时B有两种情况：把信寄给A，那么此时就只有CD两个人，而两个的时候我们已经分析了，另一种情况是不把信寄给A，此时A和B可以看作一个人，因为他们俩现在是可以寄出去一封信和收到一封信，看作一个人，此时一共是有三个人，三个人的情况我们已经分析过。所以我们的递推公式已经得到，接下来就是代码了。很简单

代码

public static int f(int i) {if(i<=2) return i-1;return (i-1)*(f(i-1)+f(i-2));
}