(moderator,add recursive to iterative category) I have to translate this recursive program into iterative, which sometimes work good sometimes not. I don't know where I'm wrong, maybe into return else condition there are some errors

this is the recursive algorithm

def algo(A, p, r, k):
    ret = False
    if(p <= r):
        if(p == r):
            ret = (k == A[p])
        else:
            q = (p   r) // 2
            ret1 = algo(A, p, q-1, k)
            ret = (k == A[p]) or ret1
            if(not ret):
                ret = algo(A, q 1, r, k)
    return ret

iterative algorithm

def iterative_algo(A, p, r, k):
    stackR = Stack()
    stackRet = Stack()
    stackQ = Stack()
    retval = False
    lastR = None
    while p <= r or not stackR.isEmpty():
        if p <= r:
            ret = False
            if(p == r):
                ret = (k == A[p])
                # ritorno
                retval = ret
                r = p-1
            else:
                q = (p   r) // 2
                ret = (k == A[q])
                if not ret:
                    stackR.push(r)
                    stackQ.push(q)
                    r = q-1
        else:
            r = stackR.top()
            q = stackQ.top()
            if lastR != r:
                ret = retval
                if not ret:
                    p = q 1
                else:
                    # ritorno
                    stackR.pop()
                    stackQ.pop()
                    retval = ret
                    lastR = r
                    r = p-1
            else:
                ret = retval
                # return
                retval = ret
                stackR.pop()
                stackQ.pop()
                lastR = r
                r = p-1
    return retval

I leave some test examples where the program loops infinitely

if __name__ == "__main__":
    #this work
    A = [1, 2,3]
    print(algo(A, 0, len(A)-1, 3))
    print(iterative_algo(A, 0, len(A)-1, 3))
    #i get loop here
    A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    print(algo(A, 0, len(A)-1, 5))
    print(iterative_algo(A, 0, len(A)-1, 5))

CodePudding user response：

Your recursive function Algo is simply searching for element k in array A, and returning True if it's found, False otherwise.

This can easily be done iteratively:

def iterative_algo(A, p, r, k):
  for i in range(p, r 1):
    if A[i] == k:
      return True
  return False

This can be written even shorted using python operator in or builtin function any:

def iterative_algo2(A, p, r, k):
  return any(A[i] == k for i in range(p, r 1))

def iterative_algo3(A, p, r, k):
  return any(a == k for a in A[p:r 1])

def iterative_algo4(A, p, r, k):
  return (k in A[p:r 1])

CodePudding user response：

Posted code is doing a recursive binary search to find if an element is in a list.

• Convert to an iterative binary search
• Use more descriptive variable names and add some comments

Code

def algo_iter(A, low, high, value):
    '''
     Binary search to check if value is in list A between index low and high
    '''
 
    mid = 0
 
    while low <= high:
        mid = (high   low) // 2
 
        # If value is greater, ignore left half
        if A[mid] < value:
            low = mid   1
 
        # If value is smaller, ignore right half
        elif A[mid] > value:
            high = mid - 1
 
        # means value is present at mid
        else:
            return True
 
    # If we reach here, then the element was not present
    return False

Test

A = list(range(5))
low = 0
high = len(A) - 1
print(algo_iter(A, low, high, 3))  # Output: True
print(algo_iter(A, low, high, 10)) # Output: False