遞迴的型別

遞迴可以分為頭遞迴或尾遞迴，具體取決於遞迴方法呼叫的放置位置。

在頭遞迴中，遞迴呼叫在它發生時，在函式中的其他處理之前（想想它發生在函式的頂部或頭部）。

在尾遞迴中，它是相反的 - 處理髮生在遞迴呼叫之前。在兩種遞迴樣式之間進行選擇可能看似隨意，但選擇可能會產生重大影響。

在路徑開頭具有單個遞迴呼叫的路徑的函式使用所謂的頭遞迴。先前展覽的階乘函式使用頭部遞迴。一旦確定需要遞迴，它首先要做的是用遞減的引數呼叫自身。在路徑末尾具有單個遞迴呼叫的函式使用尾遞迴。

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。

參考： 頭尾遞迴的區別