Convert Recursion to Iteration without stack

Question

Can someone help me convert recursion function into iterative loop , WITHOUT the use of stack so that I can implement it in O(1) auxiliary space.

    int minNumber(int a[], int low, int high) {
        if (low==high)
            return a[low];
        int mid=(low+high)/2;
        return min(minNumber(a, low, mid), minNumber(a, mid+1, high));
    }

I could not find anything on internet.

Answer 1

The code you posted takes a divide and conquer approach to finding a minimum value in an unsorted array. It will inspect every value in the array. The divide-and-conquer approach is not bringing any benefit to the solution; it only adds the cost of call-stack space. This can be replaced with a trivial linear traversal:

    int minNumber(int a[], int low, int high) {
        int result = a[low];
        for (int i = low  + 1; i <= high; i++) {
            result = min(result, a[i]);
        return result;
    }

If the intention is to call this function over the whole array, then you don't actually need the low and high parameters, as only the array's size is needed:

    int minNumber(int a[], int size) {
        int result = a[0];
        for (int i = 1; i < size; i++) {
            result = min(result, a[i]);
        return result;
    }

Side note: It is assumed that the array's size is at least 1. The minimum of an empty array is undefined, and this function would access unallocated memory if you would still call it on an empty array.