递归算法，简而言之就是一种函数调用函数自身来完成算法设计的方法。是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。

if (条件)

else

如求阶乘的递归函数：

{

reuturn 1;

return number*factorial(number-1);

函数决定终止的参数有规律地递增或递减 。

在数据结构中，链表和二叉树都具备鲜明的递归特性。

2 递归消除

2.1 利用栈结构消除递归

2.2 尾递归消除法

2.3 迭代法 Iterative Method

利用迭代算法解决问题，需要做好以下三方面的工作：

• 建立迭代关系式

• 递归用的是选择结构，迭代则是采用循环结构：

  {

  for(unsigned long i = number; i>=1; i--)

  return result;

  对于大多数常用的递归都有简单、等价的迭代程序。究竟使用哪一种，凭你的经验选择。

  递归程序逻辑清晰，但往往效率较低(空间复杂度高)。

  3 迭代和递归对比

  迭代和递归都涉及到循环，迭代显式地使用循环结构，递归通过重复的函数调用实现循环。

  递归有许多不足之处。它不断地进行函数调用，必然会增加很多开销。这样不仅消耗处理器的时间，还会消耗内存空间。每个递归调用都会创建函数的一份副本（实际上只是函数中的变量），这也会占用相当可观的内存。而迭代器通常发生在一个函数内，因此没有重复的函数调用的开销和额外的内存分配。

  4 Fibonacci函数的递归和迭代实现

  Fibonacci函数的递归实现

  {if (n==0) return 0;

  else return (f(n-1)+f(n-2));

  Fibonacci函数的迭代实现

  { int i, fn, fn_1 = 0, fn_2 = 1;

  if (n <= 0) return n;

  { fn = fn_1 + fn_2;

  return fn;

  从上面的例子可以看出，迭代比较晦涩，如果使用递归方法能够更自然地反映问题，并且能够使程序易于理解和调试，那么就可以考虑使用递归而不是迭代。

  对递归函数的每次调用都需要内存空间。由于很多调用的活动都是同时进行的，操作系统可能会耗尽可用的内存，所以应尽量避免过深的递归调用而产生溢出问题。