In my hw problem there is this code

#include <iostream>
using namespace std;
int fun(int x) {
if (x <= 0) return 0;
if (x >= 9 && x % 2 == 1) return x - 1;
if (x >= 9 || x % 3 == 0) return x - 2;
return 7;
}
int rec(int x) {
if (x < 10) return fun(x);
return rec(x / 10) + rec(x % 10);
}
int main() {
cout << fun(3) << endl; // line (a)
cout << fun(30) << endl; // line (b)
cout << fun(33) << endl; // line (c)
cout << rec(33) << endl; // line (d)
cout << rec(999) << endl; // line (e)
}

What is rec(999), I found out the answer is 24, but can someone help me understand why its 24? Thanks

Because 999 is ultimately being broken down into 3 calls of fun(9), which when added together produce 24. The recursive tree looks like this:

fun(999)
 |
 +-> fun(99)
 |    |
 |    +-> fun(9)
 |    |    |
 |    |    +-> return 8
 |    |
 |    +->fun(9)
 |        |
 |        +-> return 8
 |     
 +-> fun(9)
      |
      +-> return 8

Rewrite the code to print out debugging at the beginning and end of each function:

#include <iostream>
using namespace std;
void addSpace(int depth){
    for(int i=0;i<depth;i++)
        cout<<"  ";
}
int fun(int x, int depth) {
    int retVal=7;
    addSpace(depth); cout<<"begin fun("<<x<<"):\n";
    if (x <= 0){ retVal= 0;}
    else
        if (x >= 9 && x % 2 == 1){ retVal= x - 1;}
    else
        if (x >= 9 || x % 3 == 0){ retVal= x - 2;}
    addSpace(depth); cout<<"end fun("<<x<<"):"<<retVal<<"\n";
    return retVal;
}
int rec(int x, int depth) {
    int retVal;
    addSpace(depth); cout<<"begin rec("<<x<<"):\n";
    if (x < 10){
        retVal=fun(x,depth+1);
    }
    else{
        retVal=rec(x / 10,depth+1) + rec(x % 10,depth+1);
    }
    addSpace(depth); cout<<"end rec("<<x<<"):"<<retVal<<"\n";
    return retVal;
}
int main() {
    cout << fun(3,0) << endl; // line (a)
    cout << fun(30,0) << endl; // line (b)
    cout << fun(33,0) << endl; // line (c)
    cout << rec(33,0) << endl; // line (d)
    cout << rec(999,0) << endl; // line (e)
}

Try it. See what comes out.

Edited 4 Years Ago by DeanMSands3

This article has been dead for over six months. Start a new discussion instead.