Below is a program (in C) that I am suppose to get the results for. The recursio

Question

Below is a program (in C) that I am suppose to get the results for. The recursion I just don't understand. I want to be able to do this by hand; so I can see whats going on. The program is set up to be able to do this by hand. The output is -16. I keep messing it up by hand. Would you calculate this by hand so I can see the method.

#include
int f(int n)
{
if (n==0) return -2;
if (n==1) return 0;
if (n==2) return 1;
return 2*f(n-1) - 4*f(n-2)+4*f(n-3);
}
int main()
{
int i=4;
printf("%d ", f(i));
return 0;
}

Explanation / Answer

Note: worked out solution at bottom. explanation listed here; so for the initial value i=4, n==0? nope n==1? nope n==2? nope recursion call! return (2*f(4-1)- 4*f(4-2) +4*f(4-3)) //note: this equals: 2*f(3)-4*f(2)+4*f(1) // notice that the last two terms -4*f(2) and 4*f(1) call f and return the values: // 1 and 0 respectively. so the above equation is 2*f(3) - 4*(1) + 4*(0). //so now we need to find f(3). f passes 3 as its argument n, so f(3): n==0? nope n==1? nope n==2? nope recursion call #2. return ( 2*f(3-1)-4*f(3-2)+4*f(3-3)) //which equals: 2*f(2)-4*f(1)+4*f(0) //note that the next call to f actually returns a constant value for all terms. so the //above then reads return(2*(1) - 4*(0) +4*(-2)) which equals: return(-6). remember //that we were trying to find f(3). f(3) = -6. so our first recursive call now is: 2(-6)-4*(1)+4*(0) //which equals: -16. this is returned to the initial call. heres the ugly formula/recursive call equation worked out (note each line is equivalent to the next): 1: f(4) 2: 2*f(3) - 4*f(2) + 4*f(1) 3: 2*[2*f(2) - 4*f(1) + 4*f(0)] - 4*(1) + 4(0) 4: 2[2*(1) - 4(0) + 4(-2)] - 4 + 0 5: 2[-6] - 4 6: -16 so basically think "what does each call do?" and then embed the result in where the call was.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.