Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# Recursion of Fibonacci Numbers

Kelsey kelskjs
Ranch Hand
Posts: 36
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);
}
}

David Hibbs
Ranch Hand
Posts: 374
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. =)

Kelsey kelskjs
Ranch Hand
Posts: 36
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
Posts: 4118
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 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
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...

Kelsey kelskjs
Ranch Hand
Posts: 36
Am I on the right rack?

Nick George
Ranch Hand
Posts: 815
-you call a method "fibanocci," which I don't see written.
-Why does solveIt take two arguments?

David Harkness
Ranch Hand
Posts: 1646
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
• 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 ]

Kelsey kelskjs
Ranch Hand
Posts: 36
How come this isn't running right now? Isn't this what I was supposed to do?...are there areas that you can see that need to be fixed?...please help me to get this running right...

David Hibbs
Ranch Hand
Posts: 374
The first problem with your last solution is that you don't do any summing or return from solveIt.

Try something like

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 ]

David Hibbs
Ranch Hand
Posts: 374
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 ]