Hi. I wanted to make an example of splitting up recursive functions on python because python returns error if the level of a recursive function gets to deep. And somehow got this funny thing that returns the higest power of 2 from 1 to n given n. Not sure how exactly it happens. Can anyone explain it Mathematically maybe?
def example(n):
if n < 2: return 1
return example(n/2) + example(n/2)
def example2(n):
if n < 2: return 1
return example2(n/4) + example2(n/4) + example2(n/4) + example2(n/4)
print(example(100), example2(100))
# prints 64 64
print(example(1600), example2(1600))
# prints 1024 1024
Actually, your second program doesn't return the highest power of 2 less than the number. Try example2(9), which should print out 8 but instead prints 16.
For your first function, you have a base case of the number being less than 2, which means that the highest power of two less than that is 1 (given that you don't call this with n < 1, which will never happen if you start the call with n < 1). Then, notice that the largest power of 2 less than n must be twice the power of 2 less than n / 2. You can verify this by putting the numbers in binary; the largest power of 2 less than your number is the largest bit, and dividing by 2 is a bit shift right.
If you change your second function so that the base case is n < 4 => 1, then it will print out the largest power of 4 less than or equal to the current number similarly.