C++

Forum

 
Changing a recursive function into an iterator function

ritchson101 (27)
I had the following question in my exam and received 3 out of a possible 4 marks

Here is the question:

Assume the following recursive function: 
1
2
3
4
5
6
 
int f(int i)
{
	if(i < 2)
		return i;
	return f(i - 2) + f(i -1);
}


Translate this function into an iterative version:

Here is my solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
int f(int i)
{
	int prev,next,final;
	prev = 0;
	next = 1;
	if(n==1)
		final = i; //Correct- 1 mark
}

for(int i = 0; i <= n;i++) //Wrong
{
	final = prev + next;
	prev = next; //Correct- 1 mark
	next = final; //Correct- 1 mark
	
	return final;
}


Can someone help me figure out why my if statement was wrong and help me find a reduced or different solution?
MiiNiPaa (8886)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
int f(int i)
{
	int prev,next,final;
	prev = 0;
	next = 1;
	if(n==1) //What is n? Where did that came from?
		final = i;
} //dunction ends here. Everything down from here does not belong to it

for(int i = 0; i <= n;i++) //you are using n again (and you should start with 2)
{
	final = prev + next;
	prev = next;
	next = final;
	
	return final;  //Uncinditional return. Your loopo will iterate only once before returning.
}
DId you test your code? It doesn't even compile, end even if it did it does not work properly. Simple test would show you all that.
ritchson101 (27)
I fixed a couple things but now when I need to get an output of 5, Im getting 0. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
#include<iostream>
using namespace std;

int f(int i)
{
	int prev,next,final;
	prev = 0;
	next = 1;
	if(i==1)
		final = i; //Correct- 1 mark


	for(int i = 2; i <= final;i++) //Wrong
	{
		final = prev + next;
		prev = next; //Correct- 1 mark
		next = final; //Correct- 1 mark
	}
		return final;
}

int main()
{
	int ans = f(5);
	cout << ans << endl;
	return 0;
}


Whats wrong now?
MiiNiPaa (8886)
1
2
3
 
//final is uninitialized here
//Undefined behavior, anything could happen
for(int i = 2; i <= final;i++)
ritchson101 (27)
What should it be for it to work correctly?
Konstantin2 (142)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include <iostream>
#include <cmath>

using std::cout;
using std::endl;
constexpr double f1=(1+sqrt(5))/2;
constexpr double f2=(1-sqrt(5))/2;
constexpr double f3=sqrt(5);

int f(int n)
{
    return round((pow(f1, n) - pow(f2, n)) / f3);
}

int main
{
    for(int i = 0; i < 10; i++) cout << f(i) << endl;
}
Last edited on
ritchson101 (27)
Unfortunately that is not a iterative version for the recursive function given
Konstantin2 (142)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
#include <iostream>
#include <cmath>

using std::cout;
using std::endl;
constexpr double f1=(1+sqrt(5))/2;
constexpr double f2=(1-sqrt(5))/2;
constexpr double f3=sqrt(5);

int f(int n)
{
  for(int i = 0; i <= n; i++)
      return round((pow(f1, n) - pow(f2, n)) / f3);
}

int main
{
    for(int i = 0; i < 10; i++) cout << f(i) << endl;
}
Last edited on
ritchson101 (27)
Is there a way to do that in a single function?
Konstantin2 (142)
function int f(int n) is a single function
Last edited on
Topic archived. No new replies allowed.