信奥算法之再谈一次递归

之前，老韩已经通过下面的文章讲过关于递归的知识，先复习一下。

信奥算法之一文搞懂递归

后来，我们还写了汉诺塔的实现，以此来进一步理解和掌握递归。

信奥练习---一文搞懂汉诺塔

我们在前面的文档里面一再提到：不要太过于执着递归的内部实现。但是我们一定要知道这个递归的目的是什么。

比如: 要定义递归函数计算n的阶乘。

那么第一步，我们首先要确认我们要干什么，这样就能确定入参以及返回值。

// 计算n的阶乘，传入n，返回一个数字int f(int n){
}

第二步要确认这个递归什么时候结束，也就是找到这个递归的结束条件。否则就成了死循环。

// 计算n的阶乘，传入n，返回一个数字// 1的阶乘是1，当入参是1的时候，就到了递归该结束的时候了。// 2的阶乘是2，但是如果用入参为2做结束条件的话，就不能直接写 n==2时return 2；因为入参还有可能为1int f(int n){  if(n==1){    return 1;  }} 

// 如果用入参2时的结果做结束条件，那么需要考虑n==1时的场景，需要写成下面这样。int f(int n){  if(n==2){    return n; }}

第三步，明确函数的等价关系，我们要做的递归，严格意义上来说是用不同的入参在执行同一个逻辑操作。这个逻辑操作就是我们在这步要找到的。

这一步一般就要用到数学知识了。

n!=n*f(n-1)=n*(n-1)*f(n-2)=n*(n-1)*(n-2)*...*1

// 计算n的阶乘，传入n，返回一个数字// 1的阶乘是1，当入参是1的时候，就到了递归该结束的时候了。// 2的阶乘是2，但是如果用入参为2做结束条件的话，就不能直接写 n==2时return 2；因为入参还有可能为1int f(int n){ if(n==1){ return 1; }  return n*f(n-1);}

回到文章最开始的那句话：不要太过于执着递归的内部实现。我们只需要知道f(n-1)返回的是n-1的阶乘即可，至于怎么计算的，管它呢（可以理解成从n==1的结束条件反推而来）。

当然，这个只是一个最基本、最简陋的实现。老韩接下来会针对递归找一些练习题，一起学习下。