Highest Digit in a number(recursive function)

[antirsi96]

I have this example problem in my school coursebook. Could someone explain how this program works? It determines the highest digit in a number.

#include <iostream>
using namespace std;

int m(int n)
{
    int a,b;

    if(n==0)
        return 0;
    else{
        a = n%10;
        b = m(n/10);
        if(a>b)
            return a;
        else
            return b;
    }
}

int main()
{
    int n; cin>>n;
    cout<<m(n);
    return 0;
}

[Glandy]

NINJA EDIT

Ya I overlooked
m(n/10) // the m here whooooops

sec I'll explain again

Allright we'll get this ;)

It determines the highest digit via recursion

I'll just give you an example:
Let's say n = 5721:

we call m(n); then the following happens:

Call m(5721) from main:
Step 1a: check if n == 0 => false => else:
Step 2a: a = 5721 % 10; // a = 1
step 3a: b = m(5721 / 10); // => we call m here again

Call m(572) from b = m(5721 / 10)
Step 1b: check if n == 0 => false => else:
Step 2b: a = 572 % 10; // a = 2
Step 3b: b = m(572 / 10); // => we call m here again

Call m(57) from b = m(572 / 10)
Step 1c: check if n == 0 => false = else:
Step 2c: a = 57 % 10; // a = 7
Step 3c: b = m(57 / 10); // => we call m here again

Call m(5) from b = m(57 / 10)
Step 1d: check if n == 0 => false => else:
Step 2d: a = 5 % 10; // a = 5
Step 3d: b = m(5 / 10); // => we call m here again

Call m(0) from b = m(5 / 10)
Step 1e: check if n == 0 => true =>
Step 2e: return 0;
Jump back to Step 3d
b = 0 (since the call of m returned 0)

Step 4d: check if a > b (a = 5, b = 0) => yes
Step 5d: return a;
Jump back to Step 3c
b = 5 (since the call of m from Step 5d was 5)

Step 4c: check of a > b (a= 7, b = 5) => yes
Step 5c: return a;
Jump back to Step 3b
b = 7 (since the call of m returned 7)

Step 4b: check if a > b (a=5, b = 7) => false
Step 5b: return b;
Jump back to Step 3a
b = 7 (since the call of m returned 7) (in this case it was just b not a we got ^.^)

Step 4a: check if a > b (a=1, b = 7) => false
Step 5a: return b;
Jump back to main and print 7


Sorry I made it clear now since I screwed up the first time

Have fun ;)

[antirsi96]

I understand what your're saying, but the program works with numbers higher than 99. It can accept up to 9-digit numbers, and it still shows the highest digit. I just cannot figure out how does the program work for a number like 256 or 8560981.

[Glandy]

Alright my fault I edited above ^.^

[Duthomhas]

The recursive principle is this: given a list of values, if I can do something to the first item in the list in relation to the rest of the list, I can do it to the entire list.

So, given a number like 74, you know that we can split it up (into a list of digits) using the remainder and division operators.

74 % 10 --> 4
74 / 10 --> 7

Pause to think: 4 is the first item in the list, and 7 is the rest of the list.

The largest of 4 and 7 is 7, so the answer is 7.

Let's extend: 374. Thinking a moment, our list of digits will be 4, 7, 3. We can figure out what the largest of two digits, but we can't do three, unless we do this:

Largest( 4, Largest( 7, 3 ) )

That's the trick in the algorithm. Find the largest of the first item in the list and the largest of the rest of the list. It works for numbers of any size, like 9374:

Largest( 4, Largest( 7, Largest( 3, 9 ) ) )

Now that we are thinking recursively, the trick is to know when to stop. Thinking again, we can say "That's easy, we stop when there is no more list!"

And that is the case. When the number becomes zero, there is no more list. Conveniently, the largest digit in the number 0 is 0, so any other digits (if there were any, we don't know) will be larger.

I hope this helps clear things up.