递归算法的概念

递归（Recursion）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法，其核心思想是分治策略。 递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。

关于递归算法

在日常开发中，我们使用循环语句远远大于递归，但这不能说明递归就没有用武之地，实际上递归算法的解决问题的步骤更符合人类解决问题的思路，这是递归算法的优点，同时也是它的缺点。递归算法是比较好用，但是理解起来可能不太好理解，所以在递归算法和循环算法对比中，流行一句话：人理解循环，神理解递归。当然这只是一个段子，不过也从侧面反映出递归算法不容易理解的事实。这个我自己也深有体会，就拿排序算法里面的快排和归并排序来说吧，这两种算法采用的都是分治思想来处理排序问题，所以递归在这里就出现了，如果你不理解递归算法，就去学习这两种排序算法，可能理解起来就非常费事，尽管你知道这两种排序的算法原理和它的时间及空间复杂度，但就是不知道它是如何使用递归完成的，所以学习和理解递归算法是非常有必要的。

实际上递归算法的使用场景，远不止上面说的排序算法，在链表，树，图及其他只要符合分治思想的问题中，其实都可以采用递归来处理。

递归算法的使用

我们先来看一个Java里面，如何写一个最简单的递归方法：

上面就是最简单的递归算法，但不是正确的递归算法，一旦运行起来就会抛出栈内存溢出的异常，因为没有退出条件，所以就会进入死循环中，一直都在重复调用自己。

递归调用在底层其实是对线程栈的压栈和出栈操作，每调用一次都会压栈一次，并记录相关的局部变量信息，线程栈的内存是非常有限的，而递归调用如果是无限的，那么很快就会消耗完所有的内存资源，最终导致内存溢出，这一点与空的while死循环是不一样的，单纯的死循环会大量的消耗cpu资源，但不会占用内存资源，所以不会导致程序异常。从这一点能看到递归算法其实是更加消耗系统的性能和资源的，尽管有些编程语言可以做尾递归的优化，降低递归对资源的占用程度，但并不大多数语言都可以支持的或者说很完美的支持，Java就是其中之一，并不支持尾递归的调用。

递归的强大之处在于它允许用户用有限的语句描述无限的对象。因此，在计算机科学中，递归可以被用来描述无限步的运算，尽管描述运算的程序是有限的。 这一点是循环不太容易做到的。

编写正确的递归算法，一定要有 ”归“ 的步骤，也就是说递归算法，在分解问题到不能再分解的步骤时，要让递归有退出的条件，否则就会陷入死循环，最终导致内存不足引发栈溢出异常。

下面，我们通过两个例子来学习一下，递归的使用：

例子一：求阶乘