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!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Likes 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It goes left to right, but in this case it makes no difference.
 
Mui Goku
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks! I understood now
 
Bartender
Posts: 2697
130
Google Web Toolkit Eclipse IDE Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Google Web Toolkit Eclipse IDE Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Google Web Toolkit Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Indeed that explains it better ! Now 0 does not make sense (unless we are counting parthenogenesis species).
 
Campbell Ritchie
Marshal
Posts: 70604
287
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
reply
    Bookmark Topic Watch Topic
  • New Topic