title: Infinite Fibonacci Sequence with Memoized in Java 8
body: <p>Firstly, I'm a JavaScript programmer, and fairly new to Java8 and trying the new functional feature.</p>
  
  <p>Since I expertise JS coding, I implemented my own JS lazy-functional library for proof of concept.</p>
  
  <p><a href="https://github.com/kenokabe/spacetime" rel="nofollow noreferrer">https://github.com/kenokabe/spacetime</a></p>
  
  <p>Using the library, I could write <strong>Infinite sequence of Natural numbers and Fibonacci</strong> as below: </p>
  
  <p><strong>JavaScript</strong></p>
  
  <pre><code>var spacetime = require('./spacetime');
  var _ = spacetime.lazy(); 
  
  var natural = _(function(n)   //memoized automatically
  {
    return n;    // Natural numbers is defined as the `n`th number becomes `n`
  });
  
  var natural10 = _(natural)
    .take(10)
    .compute(function(x)
    {
      console.log(x);
    });
  
  
  //wrap a recursive function to memoize
  // must be at the definition in the same scope
  var fib = _(function(n)
  {
    if (n &lt;= 1)
      return 1; // as the Fib definition in Math
    else
      return fib(n - 2) + fib(n - 1); // as the Fib definition in Math
  });
  
  var fib10 = _(fib)
    .take(10)
    .compute(function(x)
    {
      console.log(x);
    });
  </code></pre>
  
  <p>Clear enough. The point is that I can define Natural/Fibonacci infinite sequence as the math definition as it is, then later compute the required part of the infinite sequence with lazy-evaluation.</p>
  
  <p>So, now I wonder if I can do the same manner with Java8.</p>
  
  <p>For natural sequence, I had post another Question here.</p>
  
  <p><a href="https://stackoverflow.com/questions/26277330/infinite-sequence-of-natural-numbers-with-java8-generator">Infinite sequence of Natural numbers with Java8 generator</a></p>
  
  <p>One of the way to define Natural sequence is to use <code>iterator</code> of Java8:</p>
  
  <p><strong>Java8</strong></p>
  
  <pre><code>IntStream natural = IntStream.iterate(0, i -&gt; i + 1);
  
  natural
   .limit(10)
   .forEach(System.out::println);
  </code></pre>
  
  <p>I observe <code>IntStream natural = IntStream.iterate(0, i -&gt; i + 1);</code> is a fair definition of natural numbers in math sense.</p>
  
  <p>However, I wonder if it's possible to define it as I did before, that is,</p>
  
  <p><strong>JavaScript</strong></p>
  
  <pre><code>var natural = _(function(n)   //memoized automatically
      {
        return n;    // Natural numbers is defined as the `n`th number becomes `n`
      });
  </code></pre>
  
  <p>because this looks more concise. Unfortunately, the answers suggest it's probably not possible even we use <code>generate</code>.</p>
  
  <p>In addition, <code>IntStream.iterate</code> does not fit for Fibonacci sequence.</p>
  
  <p>I seek web to <code>generate</code> indefinite sequence of  Fibonacci, the best results I found are</p>
  
  <p><a href="http://blog.informatech.cr/2013/05/08/memoized-fibonacci-numbers-with-java-8/" rel="nofollow noreferrer">http://blog.informatech.cr/2013/05/08/memoized-fibonacci-numbers-with-java-8/</a></p>
  
  <p><strong>Java8</strong></p>
  
  <pre><code>private static Map&lt;Integer,Long&gt; memo = new HashMap&lt;&gt;();
  static {
     memo.put(0,0L); //fibonacci(0)
     memo.put(1,1L); //fibonacci(1)
  }
  
  //And for the inductive step all we have to do is redefine our Fibonacci function as follows:
  
  public static long fibonacci(int x) {
     return memo.computeIfAbsent(x, n -&gt; fibonacci(n-1) + fibonacci(n-2));
  }
  </code></pre>
  
  <p>This is not an infinite sequence (lazy <code>Stream</code> in Java8).</p>
  
  <p>and</p>
  
  <p><a href="https://stackoverflow.com/questions/21650155/providing-limit-condition-on-stream-generation">Providing Limit condition on Stream generation</a></p>
  
  <p><strong>Java8</strong></p>
  
  <pre><code>Stream.generate(new Supplier&lt;Long&gt;() {
      private long n1 = 1;
      private long n2 = 2;
  
      @Override
      public Long get() {
          long fibonacci = n1;
          long n3 = n2 + n1;
          n1 = n2;
          n2 = n3;
          return fibonacci;
      }
  }).limit(50).forEach(System.out::println);
  </code></pre>
  
  <p>This is an infinite sequence (lazy <code>Stream</code> in Java8), and you could say it's defined as Math.
  However I do not like this implementation because, as you can see, there are many internal valuable to obtain the sequence such as <code>n1</code> <code>n2</code> <code>n3</code> then <code>fibonacci</code>, accordingly the code structure is complicated and <strong>you need to control mutable state which is anti-functional</strong> manner - unlike the math definition, and probably this is not memoized.</p>
  
  <p>So, here's my question. With Java8 <code>Stream</code>, is there any way to write a code to define the infinite sequence of fibonacci in concise math manner with memoization like</p>
  
  <p><strong>JavaScript</strong></p>
  
  <pre><code> var fib = _(function(n)
      {
        if (n &lt;= 1)
          return 1; // as the Fib definition in Math
        else
          return fib(n - 2) + fib(n - 1); // as the Fib definition in Math
      });
  </code></pre>
  
  <p>Thanks for your thought.</p>