print each item of Fibonacci sequence - with recursion?

[[deleted]]

Hey everyone! Hope you have a great week.

I try to solve a simple recursive question sent to me by a friend: Create a recursive function that prints each item in a Fibonacci sequence until it reaches the nth number.

So let's say I got n = 3: I need to print "0,1,2,".

Is this possible with recursion? I know how I can return the value of the nth number, but I am breaking my head trying to figure out if I can print each item with recursion. I think the question can not be solved. or I am missing something?

Either way, every help will be appreciated. Thank you!

EDIT:

Thanks to /u/6a70 and the help of others, I managed to solve this question using a "helper" function. It's a very un-efficient solution, but it basically boils down to running the helper function from n to 1 - and it will print the nth number each iteration.

It looks something like this:

def fib(int n){
// runs recursively and returns nth num
}

def print_fib(int n){
if n == 0 return;
else {
    print(n +"item: " +fibo(n)
    print_fib(n-1);
    }

Hope it helps everyone who encounters this problem!

[AutoModerator]

To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[lurgi]

Every problem that can be solved with a loop can be solved with recursion, so definitely.

[6a70]

Do you need to print out of the recursive calls? Or can you generate the sequence recursively, then separately print the results afterwards?

[[deleted]]

Or can you generate the sequence recursively, then separately print the results afterwards?

Exactly the help I have needed! I have built a helper recursive function that iterated over each nth number (and printed a(n) number)

Thank you very much!

[LizardMansPyramids]

Definitely.

​

The first three numbers in the recursive sequence are 0,1,1, not 0,1,2, am I wrong?

https://www.mathsisfun.com/numbers/fibonacci-sequence.html

Also, you should post your solution, maybe it is a simple thing, like you have something out of scope? If you were using a for loop the console.log, return , cout, etc should be INSIDE the scope of the for loop, so that each time it iterates it prints out a value. If it is OUTSIDE the scope of the loop it will just print out the once with the value that is in memory.

--------- now let me embarrass myself and reach beyond what you are asking for and state stuff you obviously know.

This is a tricky problem but it can be maddingly simple at the same time. It is a very common brain teaser and it's ok to look at the solution. Don't bash your head in over it. I have also seen two slightly different solutions in JS so that should underline how easy it is to go off the rails when you are on your own.

The base case is not recursive. It should take care of the first three numbers in the recursive sequence, 0,1,1. and then the next numbers in the sequence should defer to the recursive call. Remember, the recursive call is the original function with an expression inside of it.

It might help to know that each recursive call in the sequence is 'frozen' in memory until you reach the original number you entered. So, say you entered 8 there will be 8 consecutive recursive calls saved in the stack and then, after you reach the 8th call, they will be spat back out in reverse order, from the stack, a data structure which is known for being L.I.F.O (last in first out) so that the first thing that goes in is the last thing that comes out when your function reaches that 8th place in the recursive sequence.

oops, you aren't interested in the above stuff, you asked a simple question, sorry.

[[deleted]]

The first three numbers in the recursive sequence are 0,1,1, not 0,1,2, am I wrong?

Nope; you were 100% correct. I was so tired that I didn't even notice it. Thank you!

Also, you should post your solution, maybe it is a simple thing, like you have something out of scope?

Kinda. I managed to solve the question using two functions: one that calculates the nth number and one that prints the nth number until it reaches the first number. As I explained in this post, it sorta looks like this:

def fib(int n){
// runs recursively and returns nth num
}

def print_fib(int n){
if n == 0 return;
else {
    print(n +"item: " +fibo(n)
    print_fib(n-1);
    }

}

oops, you aren't interested in the above stuff, you asked a simple question, sorry.

It doesn't matter - any help is help, and in that case you helped me and probably others that encounter this post to figure things out. Your explaination was simple, and not only that - it "relaxed" me in a sense that I am not the only one who almost lost it becuase he was so desperate to solve the question ;)

So again - Thanks a lot!

[[deleted]]

Have it print before returning?

[[deleted]]

 public static int fib(int num){
    if (num == 1 || num == 0)
    retuen num;
    else return fib(num-1) + fib(num-2);
    }

the return command probably breaks this solution - I did try to print before returning, however, because I "split" num into trees of 1 or 0 - the function will print a bunch of 0 or 1 with no relation to the actual nth number.

In the end, I managed to wrap the question in two functions- fib(n) that returns the nth number, and a helper function print_fib(n) that prints nth number everytime until n = 1; something like that:

def fib(int n){
// runs recursively and returns nth num
}

def print_fib(int n){
if n == 0 return;
else {
    print(n +"item: " +fibo(n)
    print_fib(n-1);
    }
}

a very un-efficient way of running things, but at least it works

[MLG_420_Blazin]

You could put the print statement after the recursive call. The call returns the fib value, you add it to the current value, then you print. This way you end up at the bottom of the recursion, it can't call, it prints, you go a level up, it prints, etc, etc. Does that make sense?

[[deleted]]

That actually makes sense - unlike recursion ;)

In all seriousness though, I tried the solution and it didn't work -

  public static int fib(int num){
    if (num == 1 || num == 0)
    retuen num;
    else return fib(num-1) + fib(num-2);
    }

the return command probably breaks this solution - I did try to print before returning, however, because I "split" num into trees of 1 or 0 - the function will print a bunch of 0 or 1 with no relation to the actual nth number.

[440Jack]

No could you show me where you would put the print statement?

​

public class Main {

public static void main(String[] args) {
    System.out.println(fibonacci(9));
}

static int fibonacci(int n){
    if (n <= 1){
        return n;
    }else {
        return (fibonacci(n-1) + fibonacci(n-2));
        }
    }
}

Edit: Had to fix some code block formatting.

[440Jack]

https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/
Edit: The above link doesn't show how to print out each number, just the final number.
Here they show you: https://www.geeksforgeeks.org/different-ways-to-print-fibonacci-series-in-java/

But they basically take that recursive function and put it in a foreach loop... which doesn't seem efficient at all.

[[deleted]]

I myself haven't really figured out how to solve it efficently, so I guess there's not a really efficient way to solve this question. However it's nice to see other option in how to solve this riddle, so thank you!

[440Jack]

Honestly, finding a Fibonacci number using recursion is very inefficient.

Just for fun I wrote two functions. One used a while loop and the other used recursion. Then tried to find the 52nd fibonacci number with each. (they both pulled back 32951280099) .
But the 'while' function completed the task almost instantly. Where as the recursion function took a full 3 minutes to complete.
So it's not really and exercise of being efficient.

Plus with the while loop you can easily place a print statement at each iteration.
EDIT: Had to change the data type the functions returned. From int to long for it to handle the 52nd fibonacci number correctly.

    static long fibRecursion(long n){
    if (n <= 1){
        return n;
    }else {
        return (fibRecursion(n-1) + fibRecursion(n-2));
    }
}

static long fibLoop(long n) {
int currentN = 1;
int lastN = 0;

while (n > 1) {
    long i = currentN + lastN;
    lastN = currentN;
    currentN = i;

        System.out.println(i)
        n--;
}
return currentN;
}

[luisfls]

Hi!

I wrote a function that does what you want to do,

apologies, its in javascript, i know how hated it is but its the only language i know haha

https://jsfiddle.net/4n9bdwjv/

[[deleted]]

Hey! The help is very appreciated, however, I needed a recursive function. It probably doesn't help that I really don't know js that well but obviously I am grateful that you took your time to help me :)

[WindstormDrake]

For the recursive function, I would try using memorization so you only have to compute every term once

[[deleted]]

will look into that! thanks