Simple recursive function to find missing number in a permutation This is a short and simple Python written to help me sharpen my dulling recursion skills. It expects a sorted permutation of integers n1..n2 in list format, with a single step missing (e.g., [10,11,13]). I know it does nothing to check errors; I'm more interested in theory here.

from __future__ import division
from math import ceil

def f(lis):
    A = lis[:int(ceil(len(lis))/2)]
    B = lis[int(ceil(len(lis))/2):]
    ISA = sum(range(A[0], A[0] + len(A))) # "Ideal" Sum of A
    ISB = sum(range(B[0], B[0] + len(B))) # "Ideal" Sum of B
    if sum(A) &gt; ISA:
        return f(A)
    elif sum(B) &gt; ISB:
        return f(B)
    else:
        return B[0] - 1


Any thoughts on whether or not this is a decent solution? Any suggested improvements (especially in regard to time complexity)? Is there a more performant algorithm I could compare this to as a heuristic?
As others pointed out in comments (and as usual), an iterative solution can be better. But you said you want to practice recursion, so I guess you want to stick with that.

This code:


int(ceil(len(lis))/2)



Is exactly the same as:

len(lis) // 2


Because, there's no point taking the ceiling of a list length, as it's always an integer. And you can use // to divide and throw away the remainder, which is the same thing as casting a floating point number to integer, but shorter and simpler.

You should not duplicate code. You should put the result of the above calculation only once, save it in a variable and reuse it when creating A and B.

Similarly, instead of duplicating the logic when creating ISA and ISB, it would be better to put the common logic into a function.

Some more meaningful variable and function names would be good too.