看书看得郁闷。程序设计方法学第十章算法后面习题有一道：

已知下列函数f(x)
f(0)=1
f(1)=3
f(x+2)=(x+2)*f(x) 当x>1时

证明f(x)是递归的。

郁闷死啊，这一张前面根本就没说如何证明递归，只是举了几个简单的递归的例子，然后归纳出设计递归函数的三步骤：
1）识别过程、参量和规模
2）确定原过程和规模较小过程的类似过程
3）确定终止条件

好吧，如果设计一个f(x)的递归算法是不是就能证明f(x)是递归的了呢？貌似可以，不过仔细一看，f(0) f(1)有定义，f(2)依赖于f(4)，f(3)依赖于f(5)，f(4)依赖于f(6)，这不是发散式的吗？怎么递归啊？

难道题目出错了？

更前面第一部分讲图灵机的时候说了递归函数，说图灵机能解的函数就是部分递归函数，原递归函数从属于部分递归函数。那么也就是说，只要有图灵机对应的程序，就可以证明函数是递归的！然而图灵机就是现实计算机的抽象，因此用现实的程序写一个算法也算。这个思路和上面思路一样，怎么才能把f(x)化成f(x)=h(x, f(x-n))的形式？