title: Why are Fibonacci numbers significant in computer science?
body: <p><a href="http://en.wikipedia.org/wiki/Fibonacci_number" rel="noreferrer">Fibonacci numbers</a> have become a popular introduction to recursion for Computer Science students and there's a strong argument that they persist within nature. For these reasons, many of us are familiar with them.</p>
  
  <p>They also exist within Computer Science elsewhere too; in surprisingly efficient data structures and algorithms based upon the sequence. </p>
  
  <p>There are two main examples that come to mind:</p>
  
  <ul>
  <li><a href="http://en.wikipedia.org/wiki/Fibonacci_heap" rel="noreferrer">Fibonacci heaps</a> which have better
  amortized running time than binomial
  heaps.</li>
  <li><a href="http://en.wikipedia.org/wiki/Fibonacci_search_technique" rel="noreferrer">Fibonacci search</a> which shares
  O(log N) running time with binary
  search on an ordered array.</li>
  </ul>
  
  <p>Is there some special property of these numbers that gives them an advantage over other numerical sequences? Is it a spatial quality? What other possible applications could they have?</p>
  
  <p>It seems strange to me as there are many natural number sequences that occur in other recursive problems, but I've never seen a <a href="http://en.wikipedia.org/wiki/Catalan_number" rel="noreferrer">Catalan</a> heap. </p>