Forums Register Login

Recursion of Fibonacci Numbers

+Pie Number of slices to send: Send
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);
}
}
+Pie Number of slices to send: Send
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. =)
+Pie Number of slices to send: Send
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...
+Pie Number of slices to send: Send
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
+Pie Number of slices to send: Send
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...
+Pie Number of slices to send: Send
Am I on the right rack?

+Pie Number of slices to send: Send
-you call a method "fibanocci," which I don't see written.
-Why does solveIt take two arguments?
+Pie Number of slices to send: Send
 

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 ]
    +Pie Number of slices to send: Send
    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...

    +Pie Number of slices to send: Send
    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 ]
    +Pie Number of slices to send: Send
     

    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 ]
    Roses are red, violets are blue. Some poems rhyme and some don't. And some poems are a tiny ad.
    a bit of art, as a gift, that will fit in a stocking
    https://gardener-gift.com


    reply
    reply
    This thread has been viewed 3809 times.
    Similar Threads
    New Free Online Java Compiler and Runner
    Storing the last value in a sequence?
    Online Java Editor/Compiler?
    Fibonacci
    Iterative Fibonacci Method Problem
    More...

    All times above are in ranch (not your local) time.
    The current ranch time is
    Mar 28, 2024 04:42:13.