Basic java recursion error

Question

public static long fibby(long n){
        if (n == 0){
            return 1;
        }   
        return (fibby(n/4))+(fibby(3*n/4)); 
    }    
public static void sparsetablegen(int start, int end){

          long fibbyOut = fibby(start);
          long lastFibbyOutput = fibbyOut;
          System.out.println(start+" "+fibbyOut);

          if(start != end){
              sparsetablegen(start+1, end);
              if (lastFibbyOutput == fibbyOut){
                  return;
              }
          }
    }

Disclaimer: This is an assignment for my java project and I've tried multiple approaches and can not figure out a working solution. I will post what my understanding of the code is and what's not working properly.

What my table is supposed to do is take in values, starting from "int start" and finishing at int "end", those values will then be solved by my "fibby" function. Then it should print the values of "start" and fibbyOut side by side until it hits the "end". What I'm supposed to do is skip over any duplicate values of fibbyOut So for example I might see: 1 -> 2 2 -> 3 3 -> 4 4 -> 6 5 -> 6 6 -> 8

And so then I would want to skip over the start value 5, since fibbyOut for 4 is 6 and that's a duplicate value. So instead I should see 1-> 2 2-> 3 3-> 4 4-> 6 6-> 8

I know it's a very basic problem, but I just can't seem to figure how to remove the duplicate values of fibbyOut. Thanks for any help.

I see no recursion here - based on your question, perhaps you meant duplication (in the sense that the data values may recur). Recursion has a very different meaning for codecutters. — paxdiablo
– paxdiablo, Commented May 22, 2017 at 0:57
as a side note this --> if (lastFibbyOutput == fibbyOut) is always true. — Ousmane D.
– Ousmane D., Commented May 22, 2017 at 0:58
You should include the original problem statement so that we know what you are supposed to be solving. — Tim Biegeleisen
– Tim Biegeleisen, Commented May 22, 2017 at 0:58
I think I'd also ask for the original problem statement. It's commendable to try to restate it in your own words, but your description has me very confused. I think you're trying to say that you should skip (not recalculate) values in your table of Fibonacci numbers, but I'm really not sure. — markspace
– markspace, Commented May 22, 2017 at 1:05

Fluffy the Togekiss · Accepted Answer · 2017-05-22 02:05:31Z

1

MASSIVE EDIT: After coming to the understanding of what the problem truly was, I typed out this:

package Main;

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Long> outputs = new ArrayList<>();
        table(0, 8, outputs);
    }

    public static void table(int start, int end, List<Long> outputs) {
        outputs.add(fibby(start));
        long lastFibbyOutput = outputs.get(outputs.size() - 1);

        for(int i = outputs.size() - 2; i >= 0; i--) {
            if(outputs.size() == 1) {
                System.out.println(start + " " + lastFibbyOutput); //Always print the first time because it will be a unique value.
                break;
            } else if(outputs.get(i) == lastFibbyOutput) {
                //One of the values matches a previous one, so we break
                break;
            }

            //We're at the end without breaking, so we print.
            if(i == 0) System.out.println(start + " " + lastFibbyOutput);
        }

        if(start == end) {
            return;
        }

        start++;
        table(start, end, outputs);
    }

    public static long fibby(long n) {
        if(n == 0) return 1;

        return (fibby(n/4) + fibby(3 * n / 4));
    }
}

edited May 22, 2017 at 2:05

answered May 22, 2017 at 1:04

Fluffy the Togekiss

3252 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Noob123 Over a year ago

I added my fibby function. Thanks a lot.

Fluffy the Togekiss Over a year ago

Well, that complicates things a bit. :) I'll take a closer look.

Fluffy the Togekiss Over a year ago

Also, what does sparsetablegen do?

Fluffy the Togekiss Over a year ago

Does that solve your problem? I used an ArrayList (my friggin' favorite part of Java--it solves so many problems), which wasn't a part of your original design, but it gets the job done for dynamic storage of outputs. I tested the output, and I saw that five and seven were properly omitted.

Noob123 Over a year ago

Yeah that's great. Thank you so much for helping.

|

Collectives™ on Stack Overflow

Basic java recursion error

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related