Win a copy of Zero to AI - A non-technical, hype-free guide to prospering in the AI era this week in the Artificial Intelligence and Machine Learning forum!
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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Liutauras Vilda
• Paul Clapham
• Bear Bibeault
• Jeanne Boyarsky
Sheriffs:
• Ron McLeod
• Tim Cooke
• Devaka Cooray
Saloon Keepers:
• Tim Moores
• Tim Holloway
• Jj Roberts
• Stephan van Hulst
• Carey Brown
Bartenders:
• salvin francis
• Scott Selikoff
• fred rosenberger

Confusion in the recursive calls

Greenhorn
Posts: 5
I have been trying to write a Fibonacci series program recursively and I also got the output after searching online.

The code is:

But I am getting confused in the return statement, for example, if n=5 then the return statement will be
Which function is recursively called first? Or is it that the first recursive call gets executed first and after it has returned the final output, the second recursive call gets executed, or maybe both of them are called simultaneously?

Any help will be appreciated

Master Rancher
Posts: 4699
49
• 3
It goes left to right, but in this case it makes no difference.

Mui Goku
Greenhorn
Posts: 5
Thanks! I understood now

Bartender
Posts: 2697
130
• 1
When using recursion, a well placed logger can give you a lot of information.
e.g.

Output: Having said that, I am not sure what the intention of this method is. It says fibonacci, but when I pass 4 to it, it returns 3. Given that fibonacci series are as follows : 0, 1, 1, 2, 3, 5, 8, 13, 21, ... ,
What does the returned value indicate ?

Marshal
Posts: 70604
287
• 1
You do realise that naïve Fibonacci calculating technique is notorious for its inefficiency? It runs in exponential time.
I am also not sure I agree with Salvin about what a Fibonacci series contains. I don't believe there s such a thing as fib(0); the first two element of the series are 1, 1. Also, what you have is the classic Fibonacci series; it is possible to start a Fibonacci series with any two numbers.There are other techniques that run in linear time, and Kaldewaij has a solution running in logarithmic time.

Rancher
Posts: 214
16
• 1
Hopefully it's just being done as a learning exercise - it's a popular one since recursive Fibonacci number is a fun one to write.

If you actually need the number, you can even do it in constant time using Binet's formula (approximation but very accurate with more decimal places).

Marshal
Posts: 25930
69

Campbell Ritchie wrote:I don't believe there s such a thing as fib(0); the first two element of the series are 1, 1.

Sure there is. Work backwards from 1, 1 following the rule that each element is the sum of the previous two and you'll see that the series goes like

..., 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5...

Mui Goku
Greenhorn
Posts: 5

What does the returned value indicate?

The return value indicates the indices of the Fibonacci series, for example, if you pass 5 as the value it will return 5 as at index 5 the value is 5, and for value 6 it will return 8

salvin francis
Bartender
Posts: 2697
130
• 1

Campbell Ritchie wrote:... I am also not sure I agree with Salvin about what a Fibonacci series contains. I don't believe there s such a thing as fib(0); the first two element of the series are 1, 1...

I looked up wiki and found this: Fibonacci_number. They do mention about F0 as a part of the Fibonacci sequence. Is there any particular reason why it's not a good idea to include 0 or consider 0 as F0 ?

Here's what wiki mentions:

wiki wrote:In mathematics, the Fibonacci numbers, commonly denoted Fn, form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F0 = 0,   F1 = 1
and
Fn = Fn-1 + Fn-2
for n > 1.
The beginning of the sequence is thus: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Mui Goku wrote:The return value indicates the indices of the Fibonacci series, for example, if you pass 5 as the value it will return 5 as at index 5 the value is 5, and for value 6 it will return 8

Thanks that clears my question. This means that the input 'n' represents the index of the series. I hope adding loggers clears your original doubt.

Campbell Ritchie
Marshal
Posts: 70604
287
• 1
If I remember correctly, Fibonacci himself started from 1. He was trying to work out how many rabbits a field would contain if he started with one rabbit (well, more precisely one pair: one buck and one doe).

salvin francis
Bartender
Posts: 2697
130
Indeed that explains it better ! Now 0 does not make sense (unless we are counting parthenogenesis species).

Campbell Ritchie
Marshal
Posts: 70604
287
• 1

salvin francis wrote:. . . . parthenogenesis species.

No, even that wouldn't be 0; It would be half a pair, so fib(0) = ½

 For my next trick, I'll need the help of a tiny ad ... the value of filler advertising in 2020 https://coderanch.com/t/730886/filler-advertising