c++请教一个简单的递推问题！！！

你的公式错了,应该是
f(n)=(n-1) {f(n-1)+f(n-2)}
思路如下:
用A、B、C……表示n个信封，a、b、c……表示n份信。把错装的总数为记作f(n)。假设把a错装进B里了，包含着这个错误的一切错装法分两类：
（1）b装入A里，这时每种错装的其余部分都与A、B、a、b无关，应有f(n-2)种错装法。
（2）b装入A、B之外的一个信封，这时的装信工作实际是把（除a之外的）n-1份信纸b、c……装入（除B以外的）n－1个信封A、C…….因为这种情况要和(1)区分开来,所以b不能放到A,这时可以把b看成一个a',题目就成了把a',c,....放入A,C.....,要全放错,所以这时装错的方法有f(n-1)种。
总之在a装入B的错误之下，共有错装法f(n-2)+f(n-1)种。a装入C，装入D……的n－2种错误之下，同样都有f(n-2)+f(n-1)种错装法，因此:
f(n)=(n-1) {f(n-1)+f(n-2)}

其实,这个问题已经有通项公式了,百度出来的推导如下:
n个相异的元素排成一排a1,a2,...,an,且ai(i=1,2,...,n)不在第i位的排列数为n!(1-1/1!+1/2!-1/3!+...+(-1)^n*1/n!)
证明：
设1,2,...,n的全排列t1,t2,...,tn的集合为I,而使ti=i的全排列的集合记为Ai(1<=i<=n),
则Dn=|I|-|A1∪A2∪...∪An|.
所以Dn=n!-|A1∪A2∪...∪An|.
注意到|Ai|=(n-1)!,|Ai∩Aj|=(n-2)!,...,|A1∩A2∩...∩Am|=0!=1.
由容斥原理：
|A1∪A2∪...∪An|=n(n-1)!-C(n,2)(n-2)!+C(n,3)(n-3)!-...+(-1)^(n-1)C(n,n)*0!
=n!(1/1!-1/2!+...+(-1)^(n-1)*1/n!),
所以
Dn=n!(1-1/1!+1/2!-1/3!+...+(-1)^n