CareerCup

This is a simple dynamic programming question. Recursion is very bad in this case ( you repeatedly compute the same things).

arr[0] = 0;
arr[1] = 1;

for(int i=2; i<=n; i++)
{
	arr[i] = arr[i-2] + arr[i-1];
	printf("%d\n", arr[i]);
}

will print all f()s till n.

Based on the original, what it f(2)? Or am I missing something obvious

Actually we need one more initial condition that is f(-1)..or there is a typing error in the question

I guess the reason why he modified the question is that your recursive solution did not keep those f(x) that have been calculated before, instead, you calculate all f(x) again and again. Then he gave you a hint that you can improve your recursive solution. I just have a guess.

Here is the solution! ;)

int funcb(int x)
{
if (x == 0)
return 1;
else if (x == 1)
return 0;
else if(x>1)
return funcb(x-2)-funcb(x-3);
else
return 0;
}

do some simple algebra
f(x+2)=f(x)-f(x-1) => f(x)=f(x+2)+f(x-1)
int f(x)
{
if x=0 return 1;
else if x=1 return 0
else return f(x+2)+f(x-1)
}

Fibonacci numbers .. but with -ve and +ve sequence

<pre lang="c++" line="1" title="CodeMonkey53228" class="run-this">#include <iostream>

using namespace std;
int funcb(int x)
{
if (x == 0)
return 1;
else if (x == 1)
return 0;
else if(x>1)
return (funcb(x-2)-funcb(x-1));
}
int main()
{
int no;
cout<<"Enter the no ";
cin>>no;
cout<<"func of %d is %d\n",no,funcb(no));
return 0;

}
</pre><pre title="CodeMonkey53228" input="yes">5
</pre>

<pre lang="c++" line="1" title="CodeMonkey56226" class="run-this">#include <iostream>

using namespace std;
int funcb(int x)
{
if (x == 0)
return 1;
else if (x == 1)
return 0;
else if(x>1)
return (funcb(x-2)-funcb(x-1));
}
int main()
{
cout<<"func of "<<5<<"is "<<funcb(5);
return 0;
}
</pre><pre title="CodeMonkey56226" input="yes">
</pre>