Why are these two algorithms for finding the n-th Fabonacci number so inefficient? : When calculating the 64th Fabonacci number, the first algorithm takes several hours, and the second one takes less than a second.

Why is the efficiency of the second algorithm so much higher than that of the first one?

They look very similar.

Please tell me why, thx :)

    def fib_divide_recursion(n):
        if n <= 2:
            return n-1
        else:
            return fib_divide_recursion(n-1) + fib_divide_recursion(n-2)

    def fib_linear_recursion(n, prev={}):
        if n <= 2:
            return n-1
        try:
            return prev[n]
        except KeyError:
            prev[n] = fib_linear_recursion(n - 1, prev) + 
                fib_linear_recursion(n - 2, prev)
            return prev[n]

