• 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Recursion question

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Hello Folks!
Can someone please break down fib method shown above. I can't understand how the magic is happening inside that recursion.
 
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Greetings,

Well first to help yourself out, you should really indent your code so that a) you can better understand it, and 2) to make it easier for other to help.

Now to your question……

Get a pad of paper and a pencil.

Now looking only on fib not the code in main.

Start with this….




So there you go, the magic of the recursive call, i.e.: the nominal cases.


fib(4) and above are for you.

-steve
 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Welcome to the Ranch
What have they told you about that recursive Fibonacci program? You realise that to work out fib(4) you call fib(2) and fib(3) and fib(3) calls fib(2), so you end up calling fib(2) twice. If you try fib(5), you call fib(3) twice and fib(2) thrice. It is a classic example of what can go wrong with recursion if you design it badly.
You can design Fibonacci programs where the number of recursive calls is proportional to the argument (so fib(12) would need 2 more calls than fib(10), but they are slightly more complicated. That is linear complexity O(n).
Kaldewaij shows a version of Fibonacci numbers where the number of calls is approximately proportional to the logarithm of n: O(logn).
What you have there runs in exponential complexity, which you can verify by adding a counter to your fib method: O(1.618ⁿ) approximately. 1.618 is the golden ratio.
 
I like you because you always keep good, crunchy cereal in your pantry. This tiny ad agrees:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic