把一元纸币换成一分、二分、五分硬币（每种至少一枚），有多少种换法？使用递归_J2SE

把一元钞票换成一分、二分、五分硬币（每种至少一枚），有多少种换法？---使用递归
我用3个for循环嵌套做了一次，但老师要求用递归，我是菜鸟，不太明白递归怎么用，求高手们指点，先谢谢啦~

------解决方案--------------------------------------------------------
C++代码哈

C/C++ code

#include<iostream>using namespace std;#define LEN 3int a[] = {1, 2, 5};int remain(int i){    int total = 0;    for(int j=LEN-1;j>i;j--)        total += a[j];    return total;}long dfs(int total, int i){    if(i>=3){        if(total==0)            return 1;        return 0;    }         long res = 0;    for(int num=1;total-a[i]*num>=remain(i);++num){        res += dfs(total-num*a[i], i+1);        }    return res;}int main(){    printf("%ld\n", dfs(100, 0));}
------解决方案--------------------------------------------------------
按照面值从大到小处理，一张张累加，剩下的能被最小面值整除，则是一种组合。
Java codepublic class PayType {    private static int count=0;    private static int coins[]={1,2,5};    public static void main(String[] args) {        int amount=1*100;        int coinsCount[]=new int[coins.length];        //先每种至少一张        for(int i=coinsCount.length-1;i>=0;i--)        {            amount-=coins[i];            coinsCount[i]=1;        }        //从最大开始付        pay(amount,coinsCount.length-1,coinsCount);        System.out.println("count:"+count);    }    private static void print(int coinsCount[])    {        count++;        String str="";        int total=0;        for(int i=coinsCount.length-1;i>=0;i--)        {            if(i==coinsCount.length-1)                str+=coins[i]+"*"+coinsCount[i];            else                str+="+"+coins[i]+"*"+coinsCount[i];            total+=coins[i]*coinsCount[i];        }        System.out.println(str+"="+total);    }    private static void pay(int amount,int coinIdx,int srcCoinsCount[])    {        int coin=coins[coinIdx];        int[] coinsCount=new int[srcCoinsCount.length];        for(int i=0;i<coinsCount.length;i++)        {            coinsCount[i]=srcCoinsCount[i];        }        //如果是最小一种        if(coinIdx==0)        {            //整除，则合适            if(amount%coin==0)            {                coinsCount[coinIdx]+=amount/coin;                print(coinsCount);            }            return;        }        if(amount>=coin)        {            //用下一种面值付            pay(amount,coinIdx-1,coinsCount);            //继续用当前面值付            coinsCount[coinIdx]++;            amount-=coin;            pay(amount,coinIdx,coinsCount);        }        //不够，则用下一种面值付        else        {            pay(amount,coinIdx-1,coinsCount);        }                }}