From Recursive To Iterative Function

Question

I am trying to make from f_rec (recursive function) to f_iter (iterative function) but I can't. (My logic was to create a loop to calculate the results of f_rec(n-1).

int f_rec(int n)
{
 if(n>=3)
   return f_rec(n-1)+2*f_rec(n-2)+f_rec(n-3);
 else 
   return 1;
}

int f_iter(int n)
{
}

I also think that my time complexity for the f_rec is 3^n , please correct me if I'm wrong.

Thank you

@ZoffDino I have no idea how it will differ. I mean without any overengineering. — Eldar Dordzhiev
– Eldar Dordzhiev, Commented Jan 5, 2015 at 23:29
@ZoffDino I'm sorry I can't see the difference , I'll remove the C++ tag — Oleg
– Oleg, Commented Jan 5, 2015 at 23:29
@Oleg Write my function is not a question that is on topic on SO. You can show us what you tried and what specifically are you having trouble with. — 2501
– 2501, Commented Jan 5, 2015 at 23:31

Eldar Dordzhiev · Accepted Answer · 2015-01-05 23:43:24Z

1

There are two options:

1) Use the discrete math lessons and derive the formula. The complexity (well if @Sasha mentioned it) will be O(1) for both memory and algorithm. No loops, no recursion, just the formula.

At first you need to find the characteristic polynomial and calculate its roots. Let's asssume that our roots are r1, r2, r3, r4. Then the n'th element is F(n) = A * r1^n + B * r2^n + C * r3^n + D * r4^n, where A, B, C, D are some unknown coefficients. You can find these coefficients using your initial conditions (F(n) = 1 for n <= 3).

I can explain it on russian if you need.

2) Use additional variables to store intermediate values. Just like @6052 have answered (he has answered really fast :) ).

answered Jan 5, 2015 at 23:43

Eldar Dordzhiev

5,1352 gold badges24 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Oleg Over a year ago

I'm really confused about O(1) for the run time of algorithm , could you explain please ? I thought I can't get better than O(n)

Eldar Dordzhiev Over a year ago

It's a linear homogeneous recurrence relation with constant coefficients. Like Fibonacci sequence. So you can easily derive the formula.

rcgldr Over a year ago

If I recall correctly those roots to the characteristic polynomial are often real numbers (or worse yet, irrational or transcendental), not integers, so they can't be used to get exact answers.

Eldar Dordzhiev Over a year ago

@rcgldr Why doesn't? Double works great, its precision is enough to represent even F(INT_MAX). I have no idea how long will it be calculated with the iterative version.

phoku Over a year ago

It's not strictly speaking O(1) though since evaluating the power takes non-const time (multiplications) depending on n... I forgot what the actual relation is, but would think something along the lines of O(lg n). Nitpicking, I know.

|

Baum mit Augen · Accepted Answer · 2015-01-05 23:55:28Z

1

You can always calculate the newest value from the last three. Just start calculating from the beginning and always save the last three:

int f_iter (int n) {
    int last3[3] = {1,1,1};  // The three initial values. Use std::array if C++

    for (int i = 3; i <= n; ++i) {
        int new_value = last3[0] + 2 * last3[1] + last3[2];
        last3[0] = last3[1];
        last3[1] = last3[2];
        last3[2] = new_value;
    }
    return last3[2];
}

This solution need O(1) memory and O(n) runtime. There might exist a formula that calculates this in O(1) (there most likely is), but I guess for the sake of demonstrating the iteration technique, this is the way to go.

Your solution has exponential runtime: Every additional level spawns three evaluations, so you end up with O(3^n) operations and stack-memory.

edited Jan 5, 2015 at 23:55

answered Jan 5, 2015 at 23:36

Baum mit Augen♦

50.4k25 gold badges153 silver badges187 bronze badges

2 Comments

Oleg Over a year ago

Vielen Dank ! Was I right regarding the n^3 for the recursive function ?

advocateofnone Over a year ago

I have made an EDIT for that

advocateofnone · Accepted Answer · 2015-01-05 23:47:54Z

0

The following is the idea

  int first=1,second=1,third=1; /* if n<=3 then the respective is the answer */
  for(i=4;i<=n;i++)
  {
     int next=first+2*second+third;
     first=second;
     second=third;
     third=next;
  }
  cout<<"The answer is "<<next<<endl;

Memory is O(1) and time is O(n).

EDIT Your recursive function is indeed exponential in time , to keep it linear you can make use of an array F[n], and use memoization. First initialize F[] as -1.

    int f_rec(int n)
    {
        if(n>=3)
        {
           if(F[n]!=-1)return F[n];

           F[n]=f_rec(n-1)+2*f_rec(n-2)+f_rec(n-3);
           return F[n];       
        }  

        else 
           return 1;

}

edited Jan 5, 2015 at 23:47

answered Jan 5, 2015 at 23:37

advocateofnone

2,5393 gold badges20 silver badges46 bronze badges

Comments

6502 · Accepted Answer · 2015-01-05 23:34:57Z

0

Just keep three variables and roll them over

start with a, b and c all equal to 1
at each step new_a is a + 2*b + c
roll over: new_c is b, new_b is a
repeat the required number of steps

answered Jan 5, 2015 at 23:34

6502

115k17 gold badges177 silver badges277 bronze badges

Comments

rcgldr · Accepted Answer · 2015-01-06 03:07:59Z

0

A bit of an overkill, but this can be further optimized by letting the what the variables represent change in an unfolded loop, combined with (link) Duff's device to enter the loop:

int f_iter(int n){
int a=1, b=1, c=1;
    if(n < 3)
        return(1);
    switch(n%3){
        for( ; n > 2; n -= 3){
            case 2:
                b = c + 2*a + b;
            case 1:
                a = b + 2*c + a;
            case 0:
                c = a + 2*b + c;
        }
    }
    return c;
}

edited Jan 6, 2015 at 3:07

answered Jan 6, 2015 at 2:59

rcgldr

29.4k3 gold badges41 silver badges70 bronze badges

2 Comments

Oleg Over a year ago

definitely interesting

rcgldr Over a year ago

@Oleg - Even for 64 bit unsigned integers, the max value for n is 59, so the loop could have been completely unfolded and used a switch case with 57 lines (57 cases, 59 down to 3). For 32 bit signed integers, the max value for n is 30 (28 lines in the unfolded loop). ... or the loop could have been partially unfolded to some multiple of 3, like 6, 9, 12, ... lines.

Collectives™ on Stack Overflow

From Recursive To Iterative Function

5 Answers 5

6 Comments

2 Comments

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

6 Comments

2 Comments

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related