Root valueProblem - Help

A

ali

Hi,

I'm trying to work on a recursive function that will give me root
valuefor a given number.

What i mean by root value is, if given 13, the answer is 1+3 = 4. If
given 65, the answer is 2, i.e, 6+5=11, and 1+1=2. The final answer is
always less than 10.

I've been able to work on the code, but i can get it to work for
values less than 10, example: if use 13, it gives 4. If i give 34, it
gives 7. But if i give 55, it give me 10 as the answer, instead of 1.

Here is the code:

int function(int n)
{
if ((n<9))
{
return n;
}
else
{
return ((n%10)+(function(n/10)));
}
}

Will appreciate some help on this,

Thanks,

Ali
 
B

Brooks Moses

ali said:
What i mean by root value is, if given 13, the answer is 1+3 = 4. If
given 65, the answer is 2, i.e, 6+5=11, and 1+1=2. The final answer is
always less than 10.

I've been able to work on the code, but i can get it to work for
values less than 10, example: if use 13, it gives 4. If i give 34, it
gives 7. But if i give 55, it give me 10 as the answer, instead of 1.

Here is the code:

int function(int n)
{
if ((n<9))
{
return n;
}
else
{
return ((n%10)+(function(n/10)));
}
}

Will appreciate some help on this,

You are defining the "root value" in a recursive fashion. However, your
code is not actually implementing a recursive definition (except insofar
as it recurses to do the first summation).

A simple manual trace would indicate this. 55%10 is 5. function(55/10)
is function(5) is 5. 5+5 is 10, and there you have what you say you
get.

In order to get 1, you need to call function() again on the summed
result, by replacing the last line with this:

return function((n%10)+(function(n/10)));

- Brooks
 
D

Dave Townsend

You need to recursively call your root function on the partial result if
the result is >= 10

int root( int n )
{
if (n < 9) return n;

int sum = 0;
for ( ;n ; n = n/10 )
{
sum += n % 10;

}

// this will eventually yield a value 1--9
return root(sum);
}
 
A

AlanP

Dave said:
You need to recursively call your root function on the partial result if
the result is >= 10

int root( int n )
{
if (n < 9) return n;

int sum = 0;
for ( ;n ; n = n/10 )
{
sum += n % 10;

}

// this will eventually yield a value 1--9
return root(sum);
}

Heh.. sounds like one our our homework questions :)
 
B

Brooks Moses

AlanP wrote:
[big snip]
Heh.. sounds like one our our homework questions :)

Yeah. I thought about that about 15 seconds after sending my reply -- I
shall be rather peeved if I find out that I've been doing Ali's homework
for him. Although at least he had most of the solution already done,
rather than asking for us to solve it for him from scratch.

- Brooks
 
D

Daniel T.

ali said:
I'm trying to work on a recursive function that will give me root
valuefor a given number.

What i mean by root value is, if given 13, the answer is 1+3 = 4. If
given 65, the answer is 2, i.e, 6+5=11, and 1+1=2. The final answer is
always less than 10.

Are you wanting to make it a recursive function because of a homework
requirement? If so, then OK; but if not, then I would say don't make
this a recursive function.

The amount of memory this function takes up if recursive will be a
function of the number of times it must recurse. A non-recursive version
would have a constant memory requirement and probably execute faster.

I also personally believe that non-recursive functions are easer to
understand...

unsigned root( unsigned n )
{
while ( n > 9 ) {
unsigned i = 0;
while ( n ) {
i += n % 10;
n /= 10;
}
n = i;
}
return n;
}

vs:

unsigned sub_root( unsigned n, unsigned i )
{
if ( n )
i = sub_root( n / 10, i + n % 10 );
return i;
}

unsigned root( unsigned n )
{
if ( n > 9 )
n = root( sub_root( n, 0 ) );
return n;
}

I think it is also very instructive to compare and contrast the above
two methods of solving the problem...

I've been able to work on the code, but i can get it to work for
values less than 10, example: if use 13, it gives 4. If i give 34, it
gives 7. But if i give 55, it give me 10 as the answer, instead of 1.

Here is the code:

int function(int n)
{
if ((n<9))
{
return n;
}
else
{
return ((n%10)+(function(n/10)));
}
}

Your code doesn't work because the problem requires two recursions.
 
H

Howard

ali said:
Hi,

I'm trying to work on a recursive function that will give me root
valuefor a given number.

What i mean by root value is, if given 13, the answer is 1+3 = 4. If
given 65, the answer is 2, i.e, 6+5=11, and 1+1=2. The final answer is
always less than 10.


Why use recursion at all? It's just like the old "casting out nines" method
we learned in elementary school for checking sums. All you need is the mod
(%) function, except that you want to return 9 where the modulus is 0
(except for zero itself, which I'm guessing should return zero). How about
this:

unsigned int GetRoot( unsigned int val )
{
if (val == 0)
return 0; // handle special case of zero
else
{
root = val % 9;
if (root == 0)
return 9; // handle special case of zero modulus
else
return root; // all other cases
}

-Howard
 
P

puppet_sock

Dave Townsend said:
You need to recursively call your root function on the partial result if
the result is >= 10

int root( int n )
{
if (n < 9) return n;

int sum = 0;
for ( ;n ; n = n/10 )
{
sum += n % 10;

}

// this will eventually yield a value 1--9
return root(sum);
}

Ok, maybe I'm going blind. But what happens if you call this
with a value for n of 9? I'm thinking you learn the meaning
of the word "recursive." In other words, shouldn't the test
be n < 10 rather than n < 9?
Socks
 
A

Aguilar, James

Ok, maybe I'm going blind. But what happens if you call this
with a value for n of 9? I'm thinking you learn the meaning
of the word "recursive." In other words, shouldn't the test
be n < 10 rather than n < 9?
Socks

It was probably a typo . . . calm down. You are right, it should be n < 10
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Minimum Total Difficulty 0
I need help with a program 2
Help with code plsss 0
C coding a rotate function (help me pleasee) 1
I need help with some python code 1
Taskcproblem calendar 4
HELP PLEASE 4
Function Help 1

Members online

Forum statistics

Threads
474,175
Messages
2,570,947
Members
47,498
Latest member
yelene6679

Latest Threads

Top