Module assignment: Number helper

Why this matters

Reading about functions is not the same as writing a program that uses them well. This assignment asks you to build one small program from start to finish. It has five commands, and each command is handled by its own function. You will use prototypes, a default argument, reference parameters and recursion, the same tools you studied in the lessons. You will also check your work against sample input, the way a real developer checks code before sharing it.

The assignment is also a useful test for an interview. Interviewers often give you a short spec and ask you to write the functions, then trace a sample input by hand. Practise that habit here: read the spec twice, write the prototypes first, and check each function on its own before you join them.

The spec

Your program reads commands from standard input, one command per line. It keeps reading until the input ends. For each command, it prints one line of output. Each command is a word, followed by zero or more numbers on the same line.

If the word is not one of those five, print unknown command: WORD, where WORD is the word you read. Assume an unknown word is never followed by more numbers on the same line, so you do not need to skip anything.

Sample input and expected output

Type the following into the Input box to test your work. Each line is one command.

digits 4729
power 2 10
swap 3 8
fib 10
gcd 84 36
bogus

The expected output is:

22
1024
8 3
fib(10) = 55, calls = 177
12
unknown command: bogus

Check every line against this. A common mistake is to print the right number but forget the words in the fib line, or to put a comma in the wrong place. Your output must match exactly.

Edge-case sample

Your grader also tests these inputs. Work out the answers by hand before you run the program.

power -2 3
power 7 0
digits 0
gcd 0 5
fib 0
swap -4 4

The expected output is:

-8
1
0
5
fib(0) = 0, calls = 1
4 -4

Notice three details. A negative base raised to an odd power is negative. Any number to the power 0 is 1. The number 0 has a digit sum of 0, and gcd(0, 5) is 5, because every number divides 0.

A first step: the command loop

Before any function is written, make sure you can read commands in a loop. The next program reads one word at a time and prints it. Run it with the sample input, and watch how the loop behaves. Notice that cin >> command reads one word, skipping spaces and new lines, so the numbers that follow a command are read as separate words. That is why you will read the arguments in each branch.

To run it, type digits 4729 power in the Input box, then press Run.

Input: digits 4729 power

Expected output:

command: digits
command: 4729
command: power

The loop stops when cin >> command fails. That happens when the input ends. The numbers are treated as words here, which is fine for this step. In your real program, each branch reads exactly the arguments its command needs.

The required functions

Your program must have these functions, each with a prototype above main. The names are part of the spec, because the grader reads the program only through its output, but your reviewers will read the code, so clear names matter.

1. int digitSum(int n) returns the sum of the digits of n. It must be recursive.
2. long long power(long long base, int exp) returns base raised to exp. It must be recursive, with exp == 0 as the base case.
3. void swapValues(int &a, int &b) swaps two values. It must use reference parameters.
4. void printPair(int a, int b, string sep = " ") prints two numbers separated by sep. It must use a default argument, and the default must be in the prototype only.
5. long long fib(int n, long long &calls) returns the Fibonacci number and adds one to calls each time it is called. It must be recursive, and calls must be a reference.
6. int gcd(int a, int b) returns the greatest common divisor. It must be recursive, using the rule that gcd(a, b) equals gcd(b, a % b).

Your main function reads the commands and calls these functions. It contains the if chain or the else if chain that picks the command. It must not contain the logic of any function. A main that does everything is a common reason for low marks.

Requirements checklist

Tick each item when your program meets it. Use the list to check your work before you submit.

• The program compiles with g++ -std=c++17 and no errors.
• All six functions have prototypes above main, and each is defined exactly once.
• digitSum has a base case, and it handles the input 0.
• power handles a negative base, and an exponent of 0 returns 1.
• swapValues changes the caller's variables, and the output shows the swap.
• printPair has a default separator, and the default is written only in the prototype.
• fib counts its calls through a reference, and the count matches the sample output (177 calls for fib 10).
• gcd handles a zero argument, such as gcd 0 5.
• Unknown commands print the exact text unknown command: WORD.
• The program has no global variables.
• Each command's output matches the sample output, line for line.

Grading rubric

Your work is marked against the levels below. The marks are cumulative: a solution that meets the 80% level also meets the 60% level.

60% level. The program compiles. It handles digits, power and gcd with the right output for the main sample. It has prototypes for the functions it uses. Unknown commands are reported. The output for the main sample is correct on the lines for those three commands.

80% level. Everything in the 60% level, and also swap and fib. The swap command uses swapValues with reference parameters, and it prints through printPair. The fib command prints the number of calls, and the count is correct for fib 10. The main sample gives the exact expected output. The code uses no global variables.

100% level. Everything in the 80% level, and the edge-case sample gives the exact expected output. Each recursive function has a clear base case, and each one handles 0 correctly. The main function only reads commands and calls functions. The code has clear names, short functions, and comments where the logic is not obvious. The program prints nothing extra, such as a prompt or a blank line, because the grader compares the whole output.

A solution that prints the right values but also prints a prompt such as Enter a command: is marked down. The output must match the spec exactly, and a prompt is extra output.

Hints

Try the problem yourself before opening these hints. Each hint is hidden, so you can check one step at a time.

Reference solution

Compare your program with this one only after you have finished your own. The reference is one correct way to meet the spec. Your code may use different names and structure and still be correct.

#include <iostream>
#include <string>
using namespace std;
 
int digitSum(int n);
long long power(long long base, int exp);
void swapValues(int &a, int &b);
void printPair(int a, int b, string sep = " ");
long long fib(int n, long long &calls);
int gcd(int a, int b);
 
int main() {
    string command;
    while (cin >> command) {
        if (command == "digits") {
            int n;
            cin >> n;
            cout << digitSum(n) << endl;
        } else if (command == "power") {
            long long b;
            int e;
            cin >> b >> e;
            cout << power(b, e) << endl;
        } else if (command == "swap") {
            int a, b;
            cin >> a >> b;
            swapValues(a, b);
            printPair(a, b);
        } else if (command == "fib") {
            int n;
            cin >> n;
            long long calls = 0;
            long long value = fib(n, calls);
            cout << "fib(" << n << ") = " << value << ", calls = " << calls << endl;
        } else if (command == "gcd") {
            int a, b;
            cin >> a >> b;
            cout << gcd(a, b) << endl;
        } else {
            cout << "unknown command: " << command << endl;
        }
    }
    return 0;
}
 
int digitSum(int n) {
    if (n < 10) {
        return n;
    }
    return n % 10 + digitSum(n / 10);
}
 
long long power(long long base, int exp) {
    if (exp == 0) {
        return 1;
    }
    return base * power(base, exp - 1);
}
 
void swapValues(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}
 
void printPair(int a, int b, string sep) {
    cout << a << sep << b << endl;
}
 
long long fib(int n, long long &calls) {
    calls++;
    if (n < 2) {
        return n;
    }
    return fib(n - 1, calls) + fib(n - 2, calls);
}
 
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

Testing your work

Testing is part of the assignment, not an extra step. Work through these checks in order, and fix each failure before you go on.

1. Test one command at a time. Make an input file with a single line, such as digits 4729, and check the output. Then try the next command.
2. Test the main sample. Use the six-line sample and compare every line with the expected output.
3. Test the edge-case sample. Pay attention to the negative power and the zero cases, because most mistakes show up there.
4. Trace one call by hand. Pick gcd 84 36 and write down each pair of values until the second number reaches zero. Check that your program prints the same answer you reach by hand.
5. Check the fib count. For fib 2, the calls are fib(2), fib(1) and fib(0), which makes 3 calls in total. Write the calls out, then check your program prints calls = 3.

If a result is wrong, do not change the code at random. Find the first line where the printed value differs from your hand trace, and explain to yourself why it differs. That is the debugging method from the lessons, and it works for any program.

Explaining your design

A good submission has a short comment at the top of each function, saying what it returns and what it assumes. For example, the comment for gcd can say that both inputs are 0 or more. The comment should explain a choice, not repeat the code. Write, for example, "the base case is b == 0 because a remainder of 0 means a divides b", and skip "this returns the gcd."

When you finish, answer these questions in one or two sentences each. A reviewer may ask them.

• Which function uses a reference, and why does it need one?
• Where is the base case of power, and what happens if you remove it?
• Why does printPair have a default argument, and where is the default written?
• How many calls does fib 20 make, and what would the count look like if you added a second counter for the calls made by main?

Common mistakes in this assignment

• Missing prototypes. The compiler reports error: 'digitSum' was not declared in this scope if a function is used above its definition without a prototype.
• Defaults in both the prototype and the definition. GCC reports error: default argument given for parameter 4. Keep the default in the prototype only.
• Forgetting the & on calls. Then the count stays at 0 in main, and the output shows calls = 0. Check the signature.
• Reading one number too few. If a branch reads one argument where it needs two, the next command starts in the wrong place, and every later line is wrong.
• Printing extra text. A prompt or a blank line makes the output differ from the spec.
• Integer overflow in power. The sample power 2 10 fits in an int, but a result such as power 10 18 does not. Use long long for the result, as the spec requires.
• Negative remainders in gcd. The spec says inputs are 0 or more, so this does not happen in the sample. If you extend the program to negative inputs, check the sign rules for % first.

Stretch extension

If you finish early, extend the program. Add a command sum N that adds the numbers from 1 to N, using a recursive function that you write yourself. Add a count command that counts how many commands the program has handled so far, using a static local variable in a function called countCommand. Check each extension with its own sample lines, and add the new lines to the edge-case sample.

What you now know

• A command loop reads words with cin >> command until the input ends.
• Prototypes let main sit at the top of the file, with the functions below it.
• A default argument, written in the prototype, lets a caller leave out a detail.
• A reference parameter lets a function change the caller's variable, or add to a counter the caller owns.
• A recursive function needs a base case, and each call must move toward it.
• Good testing means checking one command at a time, tracing one call by hand, and reading the edge cases.

Summary of the module: functions have a signature, a body and a return value; prototypes make the order of functions flexible; defaults and overloads let one name serve several calls; references change the caller's data; scope and lifetime decide where a name exists; and the call stack and recursion drive every function call.