Recursive function and memorization to find minimum operations to transform n to 1 I'm a new, self-taught programmer working on the Google FooBar challenge.  I've submitted my answer (code at bottom) and it was accepted, but I'd like suggestions on how to improve my solution.

Challenge: return minimum number of operations to transform a positive integer to 1. Valid operations are: n+1, n-1, or n/2.

My solution
I started with a recursive function, but ran into a runtime error with very large numbers.  I added memorization using a global variable to store values that had already been computed, but this seems inelegant.  (I think it's discouraged to use global variables?)

Suggestions on how I might improve the below solution?

paths = {1:0, 2:1}

def shortest_path(num):
    if num in paths:
        return paths[num]

    if num % 2 == 0:
        paths[num] = 1 + shortest_path(num / 2)
    else:
        paths[num] = min(2 + shortest_path((num+1)/2), 
                         2 + shortest_path((num-1)/2))
    return paths[num]

def answer(n):
    num = int(n)
    return shortest_path(num)


Test cases: 

n = 15 --&gt; 5
n = 293523 --&gt; 25
n = 191948125412890124637565839228475657483920292872746575849397998765432345689031919481254128901246375658392284756574839202928727465758493979987654323456890319194812541289012463756583922847565748392029287274657584939799876543234568903 --&gt; 1029



The input number can be up to 309 digits long hence the final test case
The problems you've encountered usually signal that the approach is not the best.

Consider the very first step in your algorithm: you are definite that if the number is even, the best action is \$n\rightarrow \frac{n}{2}\$ (why?).

Try to apply the same logic one step further. Let \$n\$ be odd. Either \$\frac{n+1}{2}\$ or \$\frac{n-1}{2}\$ is also odd (why?). The best action is to pick that which is even (why?).

As soon as you prove all the why statements, a straight-forward non-recursive algorithm is easy to obtain.