# Recursion of Fibonacci Numbers

Kelsey kelskjs

Ranch Hand

Posts: 36

posted 12 years ago

I have a question that I was curious if anyone could help me fill in the missing code, I have no idea how to go about finishing this up in order to have it completed...

I need to take as input the values for k and n and output the nth member of the k-step sequence on a line by itself...for the fibonacci numbers. I am to do this recursively. I am to implement a generalization of the fibonacci sequence called the fibonacci k-step number. The idea is to add up the previous k values to get the next, rather than just the previous two. Example sequences are like this...

k sequence

1 1,1,2,2,2,2

2 1,1,2,4,5,8

3 1,1,2,4,7,13,24,44,81

4 1,1,2,4,8,15,29,108

Again, I need to take as input the values for n and k and output the nth member orf the k-step sequence on a line by itself...

Here is what I have so far, can anyone help me see what I need to add in order to complete this? Thank you so much.

/**

* This class computes the k step Fibonacci sequence.

*

*/

public class Fibonacci {

public Fibonacci(){}

public int solveIt(int k, int n){

}

public static void main(String[] args) {

int k=4; //the default values

int n=9;

//here we look for k and n on the command line:

if(args.length ==2){

try{

k = Integer.parseInt(args[0]);

n = Integer.parseInt(args[1]);

}catch(Exception e){

System.out.println("Improper arguments. Using k="+k+" and n="+n);

}

}

else{

System.out.println("Improper arguments. Using k="+k+" and n="+n);

}

//now we do the work:

Fibonacci f = new Fibonacci();

int sol = f.solveIt(k,n);

System.out.println(sol);

}

}

I need to take as input the values for k and n and output the nth member of the k-step sequence on a line by itself...for the fibonacci numbers. I am to do this recursively. I am to implement a generalization of the fibonacci sequence called the fibonacci k-step number. The idea is to add up the previous k values to get the next, rather than just the previous two. Example sequences are like this...

k sequence

1 1,1,2,2,2,2

2 1,1,2,4,5,8

3 1,1,2,4,7,13,24,44,81

4 1,1,2,4,8,15,29,108

Again, I need to take as input the values for n and k and output the nth member orf the k-step sequence on a line by itself...

Here is what I have so far, can anyone help me see what I need to add in order to complete this? Thank you so much.

/**

* This class computes the k step Fibonacci sequence.

*

*/

public class Fibonacci {

public Fibonacci(){}

public int solveIt(int k, int n){

}

public static void main(String[] args) {

int k=4; //the default values

int n=9;

//here we look for k and n on the command line:

if(args.length ==2){

try{

k = Integer.parseInt(args[0]);

n = Integer.parseInt(args[1]);

}catch(Exception e){

System.out.println("Improper arguments. Using k="+k+" and n="+n);

}

}

else{

System.out.println("Improper arguments. Using k="+k+" and n="+n);

}

//now we do the work:

Fibonacci f = new Fibonacci();

int sol = f.solveIt(k,n);

System.out.println(sol);

}

}

David Hibbs

Ranch Hand

Posts: 374

posted 12 years ago

Try a google search for something like this. It took me all of 30 seconds to find some CompSci notes using "fibonacci sequence java recursive solution"

http://www.maths.abdn.ac.uk/~igc/tch/mx3015/notes/node43.html

It's a starting point. You're on your own from there; homework is there to teach you something. =)

http://www.maths.abdn.ac.uk/~igc/tch/mx3015/notes/node43.html

It's a starting point. You're on your own from there; homework is there to teach you something. =)

*"Write beautiful code; then profile that beautiful code and make little bits of it uglier but faster."* --The JavaPerformanceTuning.com team, Newsletter 039.

Kelsey kelskjs

Ranch Hand

Posts: 36

posted 12 years ago

I have...all morning...for 6 hours now I have googled the life out of this! haha!...I don't understand it and was hoping that someone could just help me with the code so that I can at least look at it, I learn from examples and I was hoping someone could help me this way...please...

Max Habibi

town drunk

( and author)

Sheriff

( and author)

Sheriff

Posts: 4118

posted 12 years ago

Hi Kelsey,

I think the people on this board are happy to help, but we don't want to undermine homework assignments. After all, we may have to work with you in a few years, and we'd like it better if were able to do this on your own. That being said, we really

So let's get started on that help. Can you write a simple program the demonstrates any kind of recursion?

M

I think the people on this board are happy to help, but we don't want to undermine homework assignments. After all, we may have to work with you in a few years, and we'd like it better if were able to do this on your own. That being said, we really

*are*happy to help you understand the problem.So let's get started on that help. Can you write a simple program the demonstrates any kind of recursion?

M

Kelsey kelskjs

Ranch Hand

Posts: 36

posted 12 years ago

I understand how many people thing it is a homework problem, and indeed it could be...but like I said I am just really trying to visualize how this example in the book would work...and therefore learn by putting that code into eclipse to make it work...to see the process and how each segment of the code would work...so thats why I was searching out just help on the last part of that coding...so I could move on...when I did research on the recursion part of fibonacci, All of the examples which I did find made it to where I had not 2 inputs of n and k which I need to have, in order to solve this problem...they simply did it with the:

public static int fibonacci (int n)

{

if (n == 0 || n == 1)

return n;

else

return fibonacci (n - 1) + fibonacci (n - 2);

}

but I know that I need to have the list sequence be the output on one single line from inputing a k and a n value...to find the nth sequence...I just do not know how to write the code to do so...

thats why I was just looking for the finishing touch so I could move on and learn more material...thank you...

public static int fibonacci (int n)

{

if (n == 0 || n == 1)

return n;

else

return fibonacci (n - 1) + fibonacci (n - 2);

}

but I know that I need to have the list sequence be the output on one single line from inputing a k and a n value...to find the nth sequence...I just do not know how to write the code to do so...

thats why I was just looking for the finishing touch so I could move on and learn more material...thank you...

Nick George

Ranch Hand

Posts: 815

David Harkness

Ranch Hand

Posts: 1646

posted 12 years ago

Yes, and that's what we wanted to see. Your first code block just did the basic parameter handling which has nothing to do with recursion like you asked. You're very nearly there, in fact.

With the standard (k=2) Fibonacci sequence we have

f(0) = 0 f(1) = 1 f(n) = f(n-1) + f(n-2)

Your four stop conditions are specific to the f(k=4) sequence. You need to generalize to any k.

f(0) = 0 f(1) = 1 f(2) = f(1) + f(0) ... f(k-1) = f(k-2) + ... + f(0) f(n) = f(n-1) + f(n-2) + ... + f(n-k)

Thus, your list of stop conditions and the recursive call calculation must both be dynamic, for example a for-loop based on k. Note that f(2) ... f(k-1) are partial calculations (sum of less than k previous numbers).

Try to turn that into Java and come back with more questions.

[ September 17, 2004: Message edited by: David Harkness ]

Originally posted by Kelsey kelskjs:

Am I on the right rack?

Yes, and that's what we wanted to see. Your first code block just did the basic parameter handling which has nothing to do with recursion like you asked. You're very nearly there, in fact.

With the standard (k=2) Fibonacci sequence we have

Your four stop conditions are specific to the f(k=4) sequence. You need to generalize to any k.

Thus, your list of stop conditions and the recursive call calculation must both be dynamic, for example a for-loop based on k. Note that f(2) ... f(k-1) are partial calculations (sum of less than k previous numbers).

Try to turn that into Java and come back with more questions.

[ September 17, 2004: Message edited by: David Harkness ]

Kelsey kelskjs

Ranch Hand

Posts: 36

David Hibbs

Ranch Hand

Posts: 374

posted 12 years ago

The first problem with your last solution is that you don't do any summing or return from solveIt.

Try something like

I changed your variables.

a) don't use k; it was a parameter. You really don't want to deal with changing parameters here.

b) you're looping k times where k is the Fibonacci order -- not N times.

It's been pointed out your code assumes k=2 in the if n=... clauses.

I would suggest solving this problem by checking if( n <= k ) and writing a generic return.

BTW, it might be interesting for you to note that before you reach K,

value(n+1) = 2*value(n) where (n > 2)

[ September 20, 2004: Message edited by: David Hibbs ]

Try something like

I changed your variables.

a) don't use k; it was a parameter. You really don't want to deal with changing parameters here.

b) you're looping k times where k is the Fibonacci order -- not N times.

It's been pointed out your code assumes k=2 in the if n=... clauses.

I would suggest solving this problem by checking if( n <= k ) and writing a generic return.

BTW, it might be interesting for you to note that before you reach K,

value(n+1) = 2*value(n) where (n > 2)

[ September 20, 2004: Message edited by: David Hibbs ]

*"Write beautiful code; then profile that beautiful code and make little bits of it uglier but faster."* --The JavaPerformanceTuning.com team, Newsletter 039.

David Hibbs

Ranch Hand

Posts: 374

posted 12 years ago

Oh, BTW, you might want to recheck your sequences above. I think you'll find them in error, which could easily cause some frustration when trying to verify your results...

1 1,1,

2 1,1,2,

3 1,1,2,4,7,13,24,44,81

4 1,1,2,4,8,15,29,

What I find interesting is that the only one that was right was the Tribonacci...

[ September 20, 2004: Message edited by: David Hibbs ]

Originally posted by Kelsey kelskjs:

k sequence

1 1,1,2,2,2,2

2 1,1,2,4,5,8

3 1,1,2,4,7,13,24,44,81

4 1,1,2,4,8,15,29,108

Oh, BTW, you might want to recheck your sequences above. I think you'll find them in error, which could easily cause some frustration when trying to verify your results...

1 1,1,

**1,1,1,1**

2 1,1,2,

**3**,5,8

3 1,1,2,4,7,13,24,44,81

4 1,1,2,4,8,15,29,

**56**...

What I find interesting is that the only one that was right was the Tribonacci...

[ September 20, 2004: Message edited by: David Hibbs ]

*"Write beautiful code; then profile that beautiful code and make little bits of it uglier but faster."* --The JavaPerformanceTuning.com team, Newsletter 039.