This week's book giveaway is in the Mac OS forum.
We're giving away four copies of a choice of "Take Control of Upgrading to Yosemite" or "Take Control of Automating Your Mac" and have Joe Kissell on-line!
See this thread for details.
The moose likes Java in General and the fly likes Recursion of Fibonacci Numbers Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


JavaRanch » Java Forums » Java » Java in General
Bookmark "Recursion of Fibonacci Numbers" Watch "Recursion of Fibonacci Numbers" New topic
Author

Recursion of Fibonacci Numbers

Kelsey kelskjs
Ranch Hand

Joined: Nov 07, 2003
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

Joined: Dec 19, 2002
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. =)


"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

Joined: Nov 07, 2003
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

Joined: Jun 27, 2002
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


Java Regular Expressions
Kelsey kelskjs
Ranch Hand

Joined: Nov 07, 2003
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

Joined: Nov 07, 2003
Posts: 36
Am I on the right rack?

Nick George
Ranch Hand

Joined: Apr 04, 2004
Posts: 815
-you call a method "fibanocci," which I don't see written.
-Why does solveIt take two arguments?


I've heard it takes forever to grow a woman from the ground
David Harkness
Ranch Hand

Joined: Aug 07, 2003
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

    Joined: Nov 07, 2003
    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

    Joined: Dec 19, 2002
    Posts: 374
    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 ]
    David Hibbs
    Ranch Hand

    Joined: Dec 19, 2002
    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 ]
     
    It is sorta covered in the JavaRanch Style Guide.
     
    subject: Recursion of Fibonacci Numbers