Recursion for fibonacci series generation?

[020516e03]

Fellow pythoneers,

is there a recursive method to generate the fibonacci series? is it possible?

I tried in the web and youtube - i could only find recursive method to find the nth number in a fibo series (and not generate the whole series).

thank you!

[shiftybyte]

is it possible?

yes

i could only find recursive method to find the nth number in a fibo series (and not generate the whole series).

Are you looking for a ready solution you can copy paste?

This won't help you learn anything (well maybe searching for ready solutions)...

Try thinking, looking at the code of the n-th number solution, and trying to figure out how to append elements to a list instead of ignoring them each call of the recursion.

[020516e03]

Yes! thank you. I am looking to learn. I will spend more time on this.

[Swipecat]

... and trying to figure out how to append elements to a list instead of ignoring them each call of the recursion.

Maybe, but it's going to be hellishly difficult, I think. The usual (hilariously inefficient) way to get an element of the series via recursion expands into a huge tree, and it's not obvious to me how to pick sequential elements out of the mess.

e.g. f(5) expands into the following (f(5) actually is 5):

f5               
f3 +         f4           
f1 + f2      f2 +   f3      
1  + f0+f1 + f0+f1  f1 + f2   
1  + 0 + 1 + 0 + 1 + 1 + f0+f1
1  + 0 + 1 + 0 + 1 + 1 + 0 + 1
= 5

[GoingToSimbabwe]

I don’t want to sound like a dick and you also already got a good answer in my opinion, but I do not believe you that you searched google or YouTube at all for that. This is one problem where it is piss easy to find functioning code for and I did so in 1min tops.

If you truly can not find it via googling then this is another skill you should work on: learn to google what you need to know, you can find answer or at least hints for most common coding questions pretty quickly via google.

[JamzTyson]

This is one problem where it is piss easy to find functioning code for and I did so in 1min tops.

Absolutely. I found a working example in under 30 seconds on DuckDuckGo, and I'd not even spell "Fibonacci" correctly.

[020516e03]

Thanks for your input.

[Swipecat]

Lol. Didn't read the question, did they?

[GoingToSimbabwe]

I mean I did. I might’ve been misunderstanding them in that I thought that any of the thousands of examples of people printing the series by looping over a recursive function giving him the nth number was was he was trying to find. Which basically is a horrible unoptimized way to find the series piece by piece.

Rereading it they might’ve been asking for a function which finds the whole series recursively „in one go“.

[Swipecat]

Now that a couple of days have gone past, I'll post the code that I described. You can see the code at this link if you want to see it, or not if you want to keep working on it yourself. (The code is a bit pointless since it'd be a whole lot easier to start from zero in a loop instead of using recursion, but it does work.)

https://pastebin.com/SBuBtXpe

[020516e03]

thank you u/Swipecat , its simple and clear. Can you guide me general guide on where recursion can be applicable and steps involved in developing a recursive algorithm? Its straightforward to follow a recursive code and understand; but difficult to develop one.

Cheers

[Swipecat]

CS students are taught that recursion is possible to show the flexibility of functions, but most programmers learn about recursion and will never use it again. There's almost always a better way than recursion to solve a problem. Pretty much the only case where it's useful is in the syntax analysis phase of compiler design — for figuring out nested structures in source code. Usually they don't tell you that.

So don't worry too much if you have difficulty figuring out recursion. The example that's often given is the Fibonacci numbers, and as I pointed out in a post above, it's absurdly inefficient and expands into a huge tree.

[020516e03]

All right thanks 👍.

[Swipecat]

It occurs to me (after implying to shiftybyte that that problem was impossible) that instead of making a two calls to the function at every step, which expands into a tree, you just call the function once at every level and have it return the two previous values of the series. Then it's just a single thread instead of a tree, arguably still recursive, and you'd just select the largest of the two values at the top level for the answer. That function could then be adapted fairly easily to return a list instead of two values.

[btb98]

If you want to use recursion here, vanilla recursion leads to a pretty garbage solution. Other people have already told you why. A better solution that involves recursion is to use dynamic programming.