再帰Javaプログラムは値を返しません。 return文の前にprintステートメントを置くと無限の値が出力されます

Question

//inefficient recursive algorithm to find number of coins needed for a some amount 
public class bitcoin { 

    public int mincoins; 

    public static void main(String[] args) { 
     int[] coins = {1, 5, 10, 21, 25}; 
     int change = 63; 
     int min = 0; 
     min = MinCoins(coins, change); 
     System.out.println(min); 
    } 

    public static int MinCoins(int[] coins, int change) { 
     int mincoins = change; 
     int mincoins1 = 10000; 

     for (int j = 0; j <= coins.length - 1; j++) { 
      if (coins[j] == change) //base case 
       return 1; 
     } 

     //recursive call breaking into two sub problems 
     for (int i = 1; i <= (change)/2; i++) { 
      mincoins1 = (MinCoins(coins, i) + MinCoins(coins, (change - i))); 

      if (mincoins1 < change) 
       mincoins = mincoins1; 
     } 

     return mincoins; 
    } 
} 

Answer 1

これは非効率な再帰アルゴリズムです。しかし、あなたのコードを少し動かすことによって、少なくとも永遠にループすることはありません。代わりに、最終的に解決策が見つけられます（すべてのテストで、最適なコインカウントが見つかりました）。

あなたが逃した部分は、出口で失敗する基準でした。この文の場合（下記参照）の出口オン失敗を扱う

If the coin sum is more than 'change', give up. 
(For example, if you have already added 3 coins with value 25 (total 75), there are no 
coins that can help you reach 63, so stop trying to find them.) 

：この例では

if (change - coins[j] >= 0) 

public static int MinCoins(int[] coins, int change) { 
    int mindepth = 10000; 
    for (int j = 0; j < coins.length; j++) { 
     if (coins[j] == change) { 
      return 1; // end case 
     } else if (change - coins[j] >= 0) { 
      int depth = 1 + MinCoins(coins, change - coins[j]); 
      if (depth >= 0 && depth < mindepth) { 
       mindepth = depth; 
      } 
     } 
    } 
    return mindepth; 
}