刪除尾遞歸方法，從（JAVA）

我有這樣的方法：刪除尾遞歸方法，從（JAVA）

private String computePerm(int iteration) { 
     if (iteration < n + 1) { 
      return Character.toString((char) (iteration + 48)); 
     } else { 
      if (iteration % n == 0) { 
       return computePerm((iteration/n) - 1) + computePerm(((iteration - 1) % n + 1)); 
      } else { 
       return computePerm(iteration/n) + computePerm(iteration % n); 
      } 
     } 
    }

它計算由單一的廣度優先搜索遍歷引起的置換。我正在使用它來解決Post's correspondence problem。但是，我懷疑它是尾遞歸的，並且在某些問題的實例中似乎會產生醜陋的開銷。

如何在保留方法行爲的同時去除尾遞歸？

來源

2016-11-23 Fiery Phoenix

有在你的方法4所遞歸調用。這不是尾遞歸。 – shmosel

@shmosel那我該如何去掉遞歸呢？我真的不能這樣做，因爲我懷疑它會快很多。 –

誰說你可以？你爲什麼相信它會更快？ – shmosel

-1

這確實你以後（尺寸ñ的字母排列）是什麼：

private static String computePerm(int iteration) { 
    return Integer.toString(iteration, n); 
}

來源

2016-11-23 03:06:15 teppic

我不認爲這就是我一直在尋找的東西。抱歉。 –

'computePerm（）'產生你的字母表的排列，其大小爲_n_，對嗎？我假設你正在使用它來生成令牌對來測試你的解決方案。 'Integer.toString（i，radix）'和你的方法一樣。如果您想要一個針對您的問題的迭代解決方案的例子，請查看其來源，或者只需要使用該調用即可設置測試數據。 – teppic

刪除尾遞歸方法，從（JAVA）

回答

相關問題