递归的类型

递归可以分为头递归或尾递归，具体取决于递归方法调用的放置位置。

在头递归中，递归调用在它发生时，在函数中的其他处理之前（想想它发生在函数的顶部或头部）。

在尾递归中，它是相反的 - 处理发生在递归调用之前。在两种递归样式之间进行选择可能看似随意，但选择可能会产生重大影响。

在路径开头具有单个递归调用的路径的函数使用所谓的头递归。先前展览的阶乘函数使用头部递归。一旦确定需要递归，它首先要做的是用递减的参数调用自身。在路径末尾具有单个递归调用的函数使用尾递归。

public void tail(int n)              public void head(int n)
{                                       {
   if(n == 1)                             if(n == 0)
      return;                                return;
   else                                   else
      System.out.println(n);                 head(n-1);

   tail(n-1);                              System.out.println(n);
}                                        }

如果递归调用发生在方法的末尾，则称为 tail recursion。尾递归是 similar to a loop。method executes all the statements before jumping into the next recursive call。

如果递归调用发生在 beginning of a method, it is called a head recursion。method saves the state before jumping into the next recursive call。

参考： 头尾递归的区别