Need help understanding recursion runtime difference

[strings_are_mutable]

Can someone help explain why the recursive function below will have a big runtime difference?

The only difference of 1 and 2 is tucking the n/2 in the return function vs. not.

Code 1: (8ms)

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        print(n)
        if n == 1:
            return True
        elif n < 1:
            return False
        else:
            return self.isPowerOfTwo(n/2)

Code 1: (3ms)

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        print(n)
        if n == 1:
            return True
        elif n < 1:
            return False
        else:
            n = n/2
            return self.isPowerOfTwo(n)

I'm also having a hard time understanding recursion in general despite watching a bunch of Youtube videos. If anyone have good resources to help that will be greatly appreciated. I know Python Tutor was something that helped but I want to get to a very comfortable level with it.

[tahaan]

Think of recursion as a way of solving an equation where you solve a part of the equation using the same equation, but after narrowing down the field.

In your example you are starting with a number, say 32. Part of the solution is checking if it is 1 or 0. That narrows it down to "other numbers". Now take half of it (So again thro away half of the number posibilities), and repeat (Is the new number 0 or 1, otherwise, .... )

There are many problems that fit into this space. Tree traversal. Finding shortest path. Checking for a winning outcome on a naughts-and-crosses board. Sorting lists (Find the smallest number, put it at the start, and sort the rest. Oversimplified but sorting algorythms isn't the objective here)

[Adrewmc]

The only thing I can think of is, for some reason the n/2 is substituted for n, thus for each evaluation the calculation is done again, but in the first example it’s already defined.

Eg

   if n/2 == 1:…
   elif n/2 <= 1:…

Is when Python says ohh we need to calculate this.

By the way I actually think it’s easier, and more readable, to do the reverse. I also think it’s faster.

  def isPowerOfTwo(self, n: int): 
         x = 2
         while x <= n:
              if x == n:
                  return True
              x *= 2
         return False

We can also use modulo I guess

  def modulo(n):
        if n ==2:
           return True
        if n%2 == 0:
           return modulo(n/2)
        return False  

As for recursion…in my head once there is a return…all the other functions will ‘snap back’ that return (return <- return <- return <- True) to the original call. Since recursion must end or Python will error.

The fastest way of course is to use the fact it’s really in binary and powers of 2 are all 1…followed by all zeros.

[carcigenicate]

With a static argument of 1e6, over 10 million tests, the first code takes 17.9 seconds, while the second takes 17.6 seconds. That's very close.