这段最少钞票数计算代码是否完全递归？如何改写为递归实现？

考虑一套包含六种面额纸币的货币系统，面额分别为1卢比、2卢比、5卢比、10卢比、50卢比、100卢比。若输入总金额为N卢比，请编写程序计算凑出N卢比所需的最少纸币数量。

第一行输入整数T，表示测试用例总数量，后续T行每行输入一个整数N。

对每个测试用例，单独输出一行凑出金额N所需的最少纸币数量。

#include <iostream>
using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int count = 0;
        while(n>0){
            if(n>=100){
                count = count + n/100;
                n = n %100;
            }
            else if(n>=50){
                count = count + n/50;
                n = n%50;
            }
            else if(n>=10){
                count = count + n/10;
                n = n%10;
            }
            else if(n>=5){
                count = count + n/5;
                n = n%5;
            }
            else if(n>=2){
                count = count + n/2;
                n = n%2;
            }
            else if(n>=1){
                count = count + n/1;
                n = n%1;
            }
        
        }
        cout<<count<<endl;
    }
    return 0;
}

请问上述代码是否为完全递归实现？如果不是，应当如何修改使其成为完全递归的实现？

解答 #

上述代码不是完全递归实现。
现有代码全程采用迭代逻辑编写：通过两层while循环完成流程控制，不存在函数调用自身的递归结构，所有计数、取余运算都在循环迭代过程中完成，没有用到递归特性。

要修改为完全递归实现，需要把两处迭代逻辑全部替换为递归调用，不能保留任何循环结构：

1. 把内层计算单个金额N对应最少纸币数的循环，替换为递归函数：设置终止条件为金额为0时返回0，每次取当前可使用的最大面额，累加对应纸币张数后，对扣除该部分面额后的剩余金额递归计算。
2. 把外层遍历T个测试用例的循环，替换为递归逻辑：设置终止条件为剩余测试用例数为0时结束，每次读取一个金额、调用计算函数输出结果后，递归处理剩余的T-1个测试用例。

修改后的完全递归实现代码如下：

#include <iostream>
using namespace std;

// 递归计算指定金额的最少纸币数量
int countNotes(int n) {
    // 递归终止条件：金额为0时不需要纸币
    if (n == 0) return 0;
    if (n >= 100) return n/100 + countNotes(n % 100);
    if (n >= 50) return n/50 + countNotes(n % 50);
    if (n >= 10) return n/10 + countNotes(n % 10);
    if (n >= 5) return n/5 + countNotes(n % 5);
    if (n >= 2) return n/2 + countNotes(n % 2);
    return n + countNotes(0);
}

// 递归处理所有测试用例
void processCases(int t) {
    // 递归终止条件：没有剩余测试用例时结束
    if (t == 0) return;
    int n;
    cin >> n;
    cout << countNotes(n) << endl;
    processCases(t - 1);
}

int main() {
    int t;
    cin >> t;
    processCases(t);
    return 0;
}

注：该货币系统的面额为规范的贪心可解结构，上述递归实现和原迭代实现逻辑一致，都可以得到正确的最少纸币数结果。

内容的提问来源于stack exchange，提问作者BZL