find the nth fibonacci number in python

Here's a recursive solution to find the nth Fibonacci number in Python:

main.py
def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)
107 chars
6 lines

And here's a dynamic programming solution that uses memoization to avoid duplicate calculations:

main.py
def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    else:
        memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
        return memo[n]
195 chars
9 lines

Both solutions have a time complexity of O(2^n) but the dynamic programming solution has a space complexity of O(n) because it stores the previously calculated values in memo. Therefore, the dynamic programming solution is more efficient and practical for finding large Fibonacci numbers.