write iterative function to calculate a mathematics sequence-CodePudding

for a homework, I need to program two functions to calculate a same mathematics sequence, recursive and iterative version. I succeeded to program the recursive version, but I don't know how to realize the iterative version.

(It's the first time I program with C language.)

the recursive version :

float sequence(int n)
{
    float x = 1.0;
    
    if(n>=1)
    {
        float temp = sequence(n-1);
        x = temp 1/temp;
    }
    return x;
}

if the code works efficiently, I must to find sequence(0) = 1, sequence(1) = 2, sequence(3) = 2.5, sequence(4) = 2.9,..., sequence(100) ~ 14.284066.

Also, according to my professor, it's necessary the code is enough optimized (time complexity?) and without obvious semantic problems (too easy to discover).

Could you help me to realize iterative version with any suggestions?

So, if this question has already been asked, I'm sorry, could you give me the link please.

else I thank you for your time,

Sincerely.

CodePudding user response：

Your recursion works deconstructively, starting with n and working backwards with recursive calls until it gets to the base case. For the base case, it returns the known answer, and at each level above the base case it evaluates the equation using returned result.

For iteration, you want to work constructively from the base case up to n. At each iteration, the current value is used to update the result from the previous iteration.

You used the pseudocode tag, so I'm providing this in Ruby (which is practically pseudocode but can be run to check the answers). You can translate it to C for yourself to enforce your understanding.

def recursive(n)
  return 1.0 if n < 2
  x = recursive(n - 1)
  return x   1 / x
end

def iterative(n)
  x = 1.0
  n.times { x  = 1.0 / x }
  return x
end

I've tested, and both of those return identical answers for n up to 1000

CodePudding user response：

I made it out, apparently it's the Fractional Chromatic Number sequence.

#include <stdio.h>

double seqrec(unsigned n) {
    if (n < 2) return 1;
    return seqrec(n - 1)   1 / seqrec(n - 1);
}

double seqiter(unsigned n) {
    double numerator = 1, denominator = 1;
    for (unsigned k = 2; k <= n; k  ) {
        double newnumerator = numerator*numerator   denominator*denominator;
        denominator = numerator*denominator;
        numerator = newnumerator;
        // avoid nan, get numbers down to a reasonable level :-)
        while (denminator > 2) {
            numerator /= 2;
            denominator /= 2;
        }
    }
    return numerator / denominator;
}

int main(void) {
    for (int k = 1; k < 13; k  ) {
        printf("%d ==> %f, %f\n", k, seqrec(k), seqiter(k));
    }
}

With the following output

1 ==> 1.000000, 1.000000
2 ==> 2.000000, 2.000000
3 ==> 2.500000, 2.500000
4 ==> 2.900000, 2.900000
5 ==> 3.244828, 3.244828
6 ==> 3.553010, 3.553010
7 ==> 3.834462, 3.834462
8 ==> 4.095255, 4.095255
9 ==> 4.339440, 4.339440
10 ==> 4.569884, 4.569884
11 ==> 4.788708, 4.788708
12 ==> 4.997533, 4.997533