title: Find the 100th Lucas Number
body: <p>I am supposed to write a Python function which takes an argument, n, and returns the nth iteration of the Lucas sequence. I have used recursion to accomplish this, and my issue comes with the efficiency of the code. A test case the function must pass is <code>lucas(100)</code>, with an expected value of 792070839848372253127. I don't know a more efficient way to solve this, so that the program doesn't continue running forever when it gets to this case. </p>
  
  <p>This is my code:</p>
  
  <pre><code>def lucas(n):
  """Returns the nth Lucas number.
    Lucas numbers form a series similar to Fibonacci:
    2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843,...
  
  &gt;&gt;&gt; lucas(0)
  2
  &gt;&gt;&gt; lucas(1)
  1
  &gt;&gt;&gt; lucas(2)
  3
  &gt;&gt;&gt; lucas(3)
  4
  &gt;&gt;&gt; lucas(11)
  199
  &gt;&gt;&gt; lucas(100)
  792070839848372253127
  """
  "*** YOUR CODE HERE ***"
  
  
  
      if n == 0:
        return 2
      elif n == 1:
        return 1
      else:
        return lucas(n-1) + lucas(n-2)
  </code></pre>
  
  <p>If anyone could provide any help, I would really appreciate it!  </p>
  
  <p>Edit: Thanks to everyone who provided help and other solutions!!! I am new to using StackOverflow so I really appreciate it! I ended up using the following code to reach a much, much, much faster and efficient solution:</p>
  
  <pre><code>list = [2,1]
  
  for i in range(2,n+1):
      list.append(list[i-2] + list[i-1])
  
  return list[n]
  </code></pre>