# Recursive Algorithm Help

• November 11th 2009, 06:41 PM
minkyboodle
Recursive Algorithm Help
Here is the problem:

Suppose a sequence is defined recursively be setting $a_1 = 2$ and $a_2 = 9$ and, for $n\geq2$ , requiring that $a_n = 2a_{n-1} + 3a_{n-2}$.

Give a recursive algorithm for computing $a_n$, where $n$ is a positive integer.

Using the initial conditions, I could calculate $a_3 , a_4$ , etc., but that is not what the problem is asking for. I thought recursive definitions were when you set $n = 0$, but that makes the equation work with negative numbers. So, here I am, confused beyond belief with algorithms
• November 11th 2009, 11:03 PM
mkahraman
int recursiveFunc(int n){
if(n<1) return 0; //This shouldn't be
if(n==1) return 2;
if(n==2) return 9;

return ((2*recursiveFunc(n-1)) + (3*recursiveFunc(n-2)));
}

int main(){
int n;
int result;

n=100 //n is arbitrary

result=recursiveFunc(n);
}

http://www.mathhelpforum.com/math-he...cc872e77-1.gif and http://www.mathhelpforum.com/math-he...bf51fb0d-1.gif and, for http://www.mathhelpforum.com/math-he...5f63a70c-1.gif , requiring that http://www.mathhelpforum.com/math-he...42fd5941-1.gif.
• November 12th 2009, 04:44 AM
minkyboodle
Quote:

Originally Posted by mkahraman
int recursiveFunc(int n){
if(n<1) return 0; //This shouldn't be
if(n==1) return 2;
if(n==2) return 9;

return ((2*recursiveFunc(n-1)) + (3*recursiveFunc(n-2)));
}

int main(){
int n;
int result;

n=100 //n is arbitrary

result=recursiveFunc(n);
}

http://www.mathhelpforum.com/math-he...cc872e77-1.gif and http://www.mathhelpforum.com/math-he...bf51fb0d-1.gif and, for http://www.mathhelpforum.com/math-he...5f63a70c-1.gif , requiring that http://www.mathhelpforum.com/math-he...42fd5941-1.gif.

The language you used makes no sense to me
• November 12th 2009, 05:05 AM
alunw
The program that has been posted is in the computer language C, but it is a very very bad way of calculating the function. For a very similar example, and explanation of why it is bad see

Dr. Dobb's | The Case for D | June 15, 2009

Your teacher probably really does want you to come up with a solution like this, as the exercise is probably to get you familiar with the concept of a recursive function. But functions like this should absolutely not be calculated using recursion.
• November 12th 2009, 05:46 AM
mkahraman
I'm not saying this the best way and know this algorithm is very bad for computing given function.

But this is the way how to solve given problem in recursive manner.

The program i wrote is in C programming language. I didn't try if it compiles or not.

But i am sure this is the answer.
• November 12th 2009, 06:00 AM
Soroban
Hello, minkyboodle!

Are you sure of the wording of the problem?

Quote:

A sequence is defined recursively by: . $a_1 = 2,\;\; a_2 = 9, \;\; a_n \:=\:2a_{n-1} + 3a_{n-2}\;\;\text{ for }n \geq 2$

Give a (?) recursive (?) algorithm for computing $a_n$, where $n$ is a positive integer.

By my understanding, they've already given us the recursive algorithm.
. . What they want is a "closed form" for the $n^{th}$ term.

There is a procedure for determining the generating function for a linear recursion,
. . but I will wait until I get some clarification.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Well, okay . . . Here's the answer:

. . . $a_n \;=\;\frac{1}{12}\bigg[11(3^n) + 9(\text{-}1)^n\bigg]$