Is this code fully recursive? If not, how do I make it so?-CodePudding

Problem

Consider a currency system in which there are notes of six denominations, namely, Rs. 1, Rs. 2, Rs. 5, Rs. 10, Rs. 50, Rs. 100. If the sum of Rs. N is input, write a program to compute the smallest number of notes that will combine to give Rs. N.

Input

The first line contains an integer T, the total number of test cases. Then follow T lines, each line contains an integer N.

Output

For each test case, display the smallest number of notes that will combine to give N, in a new line.

#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 0;
            }
            else if(n>=50){
                count = count   n/50;
                n = nP;
            }
            else if(n>=10){
                count = count   n/10;
                n = n;
            }
            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;
}

CodePudding user response：

As pointed out you don't do any recursion, you don't do any function calls at all.

There is also a code smell.

If you remove all the else the while loop becomes obsolete.

        if(n>=100){
            count = count   n/100;
            n = n 0;
        }
        if(n>=50){
            count = count   n/50;
            n = nP;
        }
        if(n>=10){
            count = count   n/10;
            n = n;
        }
        if(n>=5){
            count = count   n/5;
            n = n%5;
        }
        if(n>=2){
            count = count   n/2;
            n = n%2;
        }
        if(n>=1){
            count = count   n/1;
            n = n%1;
        }

And you can remove all the if as well to get the same result without branching. Which might actually be faster:

            count = count   n/100;
            n = n 0;
            count = count   n/50;
            n = nP;
            count = count   n/10;
            n = n;
            count = count   n/5;
            n = n%5;
            count = count   n/2;
            n = n%2;
            count = count   n/1;
            n = n%1;

The code is very repetitive. If you put the currency nominations in an array this can be written neater:

// outside of main
constexpr std::array coins = {100, 50, 10, 5, 2, 1};

// count coins
int count = 0;
for (const auto & coin : coins) {
    count  = n / coin;
    n %= coin;
}

Now isn't that much better?

CodePudding user response：

There's no recursion in this code. Recursion is where a function calls itself (directly of indirectly).

It's actually illegal for main to call itself, so to make this code recursive you are going to have to add at least one function. Where you see a loop that's where you should think recursion. So see the while loop, turn that into a function (don't worry about recursion yet). Then when you have that working see if you can replace the while loop part, instead of looping the function just calls itself (recursively).