Find average using recursion

Question

0.00/5 (No votes)

See more:

I'm doing an exercise which reads as follows:

Create a function that given a number n the average of the steps they have to make the numbers from 1 to n to get to number 1, for example:

1 => 0 steps to get to 1
2 => 1 steps to get to 1
3 => 7 steps to get to 1
4 => 2 steps to get to 1
5 => 5 steps to get to 1

Then the average "Collatz" function would behave as follows:

[B]averageCollatz(1)[/B] == 0 / 1 == 0
[B]averageCollatz(2)[/B] == (0+1) / 2 == 0.5
[B]averageCollatz(3)[/B] == (0+1+7) / 3 == 2.6666..
[B]averageCollatz(4)[/B] == (0+1+7+2) / 4 == 2.5
[B]averageCollatz(5)[/B] == (0+1+7+2+5) / 5 == 3
etc...

I did this code

C#

unsigned int collatz(
    const unsigned int n )
{
  if ( n == 1 )
    return 0;
  else if ( n % 2 )
    return 1 + collatz( n * 3 + 1 );
  else
    return 1 + collatz( n / 2 );
}

double averageCollatz(unsigned num)
{
    double temp, total = 0;;

	temp = collatz(num);
    if ( num > 1 ) averageCollatz(num - 1);
	  total += temp;
    return total / num;
}

But it does not work as it should ¿I'm doing wrong?

Posted 22-Nov-14 1:11am

Member 11238028

Updated 22-Nov-14 1:21am

v2

Add a Solution

Comments

Afzaal Ahmad Zeeshan 22-Nov-14 7:31am

Is that a homework?

Member 11238028 22-Nov-14 7:47am

it is not an exercise I set out do

Philippe Mori 22-Nov-14 12:17pm

It is really not clear what you are trying to do.

From where do the step sequence come?
What is the meaning of "to get to 1" ?

Without understanding from where the numbers come and what you want to to with those number, we cannot help you much.

Philippe Mori 22-Nov-14 12:28pm

I have found some explanation on the web: Collatz conjecture . You should have either give that link or explain it as otherwise, most reader probably have never heard about collatz function and might not think that it is something well defined.

Andreas Gieriet 22-Nov-14 17:21pm

First: your Collatz function is not correct (see the link).
Second: I understand that the Collatz function is just a series of numbers that you use to "test" your recursive average algorithm, right? So, you could have used any series of numbers for your test (like Fibonacci, etc.), correct?
Third: if you want on any cost use recursion for average (which is a very bad choice), then you should simply add while entering the recursion and divide in the innermost by the number of elements only (assuming your sum does not go beyond the max number range). Or you could divide you intermediate results and instantly multiply by n/k, which results in nasty chain error problems...
Cheers
Andi

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Philippe Mori · Answer 1 · 2014-11-22T06:44:00

I think that the problem is that you do the division at each step. You need to do the division only once at end.

Thus averageCollatz would be renamed sumCollatz and last line would be:

C++

return total;

Then you would have:

C++

double averageCollatz(unsigned int num)
{
    unsigned steps = collatz(num);
    double sum = sumCollatz(num);
    return sum / steps; 
}

You might have to treat the case for n equals to 0.

Andreas Gieriet · Answer 2 · 2014-11-22T11:47:00

The average is the average

a = 1/m ∙ ∑_k=0^mx_k

As a series, you can define the following:

1) a₀ = x₀
2) a_n+1 = (a_n ∙ (n + 1) + x_n+1) / (n + 2)

This has the problem of the initial average function: the sum may go beyond the number limit, i.e. the term a_n ∙ (n + 1) is identical with the partial sum up to the given point.

You may now rewrite the second term above to

1) ...
2) a_n+1 = a_n ∙ (n + 1) / (n + 2) + x_n+1 / (n + 2)

This second term has another issue: it most likely produces chain-errors with the limited precision of computer arithmetic: the term (n + 1) / (n + 2) is always smaller than 1 and goes towards 1 with larger numbers n. At some point it is exactly 1 for the computer arithmetic and so produces (slightly?) wrong results.

For your given problem, you have to decide which of the above mentioned effect is worse for a given problem, and accordingly chose one of the other for your calculation. It does not matter if you do iterative or recursive approach since each recursive approach can always be done iteratively too.

In my eyes, recursion is the wrong approach here since you easily fill up the stack. Recursion is often used for divide-and-conquer approach which results in a more or less binary search depth only of the stack and not a linearly growing stack to "infinity". From that point of view, recursion is *really* the *wrong* approach for this problem.

Cheers
Andi

PS: See also my comment on the Collatz function above.

Find average using recursion

2 solutions

Solution 2

Solution 3

Add your solution here

Preview 0