By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
460,022 Members | 1,212 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 460,022 IT Pros & Developers. It's quick & easy.

Root valueProblem - Help

P: n/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
Jul 22 '05 #1
Share this Question
Share on Google+
8 Replies


P: n/a

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);
}
"ali" <tj@raha.com> wrote in message
news:et********************************@4ax.com...
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

Jul 22 '05 #2

P: n/a
ali wrote:
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

--
The "bmoses-nospam" address is valid; no unmunging needed.
Jul 22 '05 #3

P: n/a
Dave Townsend wrote:
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);
}
"ali" <tj@raha.com> wrote in message
news:et********************************@4ax.com...
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



Heh.. sounds like one our our homework questions :-)
Jul 22 '05 #4

P: n/a
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
--
The "bmoses-nospam" address is valid; no unmunging needed.
Jul 22 '05 #5

P: n/a
ali <tj@raha.com> wrote:
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.
Jul 22 '05 #6

P: n/a

"ali" <tj@raha.com> wrote in message
news:et********************************@4ax.com...
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
Jul 22 '05 #7

P: n/a
"Dave Townsend" <da********@comcast.net> wrote in message news:<K7********************@comcast.com>...
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
Jul 22 '05 #8

P: n/a

<pu*********@hotmail.com> wrote in message
news:c7**************************@posting.google.c om...
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
Jul 22 '05 #9

This discussion thread is closed

Replies have been disabled for this discussion.