programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Paul Clapham
• Tim Cooke
• Jeanne Boyarsky
• Liutauras Vilda
Sheriffs:
• Frank Carver
• Henry Wong
• Ron McLeod
Saloon Keepers:
• Tim Moores
• Frits Walraven
• Tim Holloway
• Stephan van Hulst
• Carey Brown
Bartenders:
• Al Hobbs
• Piet Souris
• Himai Minh

# Recursion of Fibonacci Numbers

Ranch Hand
Posts: 36
• • Number of slices to send:
Optional 'thank-you' note:
• • 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);
n = Integer.parseInt(args);
}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);
}
}

Ranch Hand
Posts: 374
• • Number of slices to send:
Optional 'thank-you' note:
• • 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
• • Number of slices to send:
Optional 'thank-you' note:
• • 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...

town drunk
( and author) Posts: 4118
• • Number of slices to send:
Optional 'thank-you' note:
• • 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
• • Number of slices to send:
Optional 'thank-you' note:
• • 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
• • Number of slices to send:
Optional 'thank-you' note:
• • Am I on the right rack?

Ranch Hand
Posts: 815
• • Number of slices to send:
Optional 'thank-you' note:
• • -you call a method "fibanocci," which I don't see written.
-Why does solveIt take two arguments?

Ranch Hand
Posts: 1646
• • Number of slices to send:
Optional 'thank-you' note:
• • 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
• • Number of slices to send:
Optional 'thank-you' note:
• • 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
• • Number of slices to send:
Optional 'thank-you' note:
• • 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
Posts: 374
• • Number of slices to send:
Optional 'thank-you' note:
• • 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 ] Listen. That's my theme music. That's how I know I'm a super hero. That, and this tiny ad told me: the value of filler advertising in 2021 https://coderanch.com/t/730886/filler-advertising