1

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 lucas(100), 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.

This is my 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,...

>>> lucas(0)
2
>>> lucas(1)
1
>>> lucas(2)
3
>>> lucas(3)
4
>>> lucas(11)
199
>>> lucas(100)
792070839848372253127
"""
"*** YOUR CODE HERE ***"



    if n == 0:
      return 2
    elif n == 1:
      return 1
    else:
      return lucas(n-1) + lucas(n-2)

If anyone could provide any help, I would really appreciate it!

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:

list = [2,1]

for i in range(2,n+1):
    list.append(list[i-2] + list[i-1])

return list[n]
Hammer4
  • 21
  • 4
  • 3
    This is a classic case where memoization or dynamic programming is much more efficient than a naive recursive function. See e.g. https://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_sequence – kaya3 Jan 15 '20 at 01:05
  • You are repeatedly recalculating the same values. You will need to store and retrieve them instead. – PM 77-1 Jan 15 '20 at 01:08
  • Does this answer your question? [Python program to find fibonacci series. More Pythonic way](https://stackoverflow.com/questions/578379/python-program-to-find-fibonacci-series-more-pythonic-way) – Julien Jan 15 '20 at 01:16
  • And on a _completely_ different note, while the idea here is to teach you recursion (for which fibonacci/lucas/etc is pretty much the worst example for) the much better way to compute the nth Lucas number is actually an immediate bit maths: Lucas(n) = floor(phi^n) where phi is the golden ratio. – Mike 'Pomax' Kamermans Jan 15 '20 at 01:18
  • @Mike'Pomax'Kamermans Mathematically that's correct, but with floating point numbers it won't give correct answers for larger inputs, e.g. `lucas(100)` will be wrong in the last seven places. – kaya3 Jan 15 '20 at 01:23

3 Answers3

3

Here is a faster approach. The sequence can be built up, step by step, using only the two last values.

def lucas(n):
    a, b = 2, 1
    for _ in range(n):
        a, b = b, a + b
    return a

for i in range(101):
    print(i, lucas(i))

Note that this will work quickly for n up to about 100,000. For larger n, we can make use of the doubling formulas for Fibonacci, and the relationship between Lucas numbers and Fibonacci numbers: lucas(n) = fibonacci(n-1)+fibonacci(n+1).

def fibonacci(n):
    return fibonacci_pairs(n)[0]

# returns the tuple (fib(n), fib(n+1)).
def fibonacci_pairs(n):
    if n == 0:
        return (0, 1)
    else:
        a, b = fibonacci_pairs(n // 2)
        c = a * (b * 2 - a)
        d = a * a + b * b
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, c + d)

def lucas(n):
    if n == 0:
        return 2
    else:
        return fibonacci(n+1) + fibonacci(n-1)

for i in range(101):
    print(i, lucas(i))
for i in range(7):
    print(10**i, lucas(10**i))

This also gets slow for n about 1 million. The problem is that the numbers get very large, for which arithmetic operations are slow. The millionth Lucas number is already 208988 digits long.

JohanC
  • 59,187
  • 8
  • 19
  • 45
3

You're repeatedly calculating the same values, so cache them:

@functools.lru_cache
def lucas(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        return lucas(n-1) + lucas(n-2)

Or just keep the last two around for the next one:

def lucas(n):
    a, b = 2, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Recursive version:

def lucas(n, a=2, b=1):
    return lucas(n - 1, b, a + b) if n else a
Kelly Bundy
  • 15,040
  • 7
  • 22
  • 53
  • For anyone confused as to how the values were cached, at the top of the code `@functools.lru_cache` does the job for you automatically. This is also called dynamic programming. – Kenivia Jan 15 '20 at 01:40
1

Some people will find this question because they have the same homework exercise, but some will find it because they're hoping to find an actually efficient way to compute the Lucas numbers.

For those folks: don't write a recursive function at all, you can directly compute any Lucas number with a trivial bit of maths:

golden_ratio = (1 + 5 ** 0.5) / 2

def lucas(n):
    if n == 0:
        return 2
    return round(golden_ratio ** n)

Done.

However, because we're working with IEEE floats, this is 100% correct on paper, and not 100% correct on computers at higher and higher values of n, so you may need to port this to your favourite flavour of maths-in-python (sympy, etc)

Mike 'Pomax' Kamermans
  • 44,582
  • 14
  • 95
  • 135