Write a recursive function to find the smallest element in a vector. We can not use loops but can use if statements. Using RECURSION is a must.

I Could Not think of any solution, the main problem was if I define a function then I have to give it some value and if I do so then whenever recursion occur it will again reset the value of that variable.

CodePudding user response：

function miminimumis=minimumval(k)
aa=k(1);
k=k(k<k(1));
if length(k)==0
    miminimumis=aa;
  
else
%      this line gives the recursion
     miminimumis=minimumval(k);
   
end

end
    
  

here we create a new array which consists of elements only smaller than the first element. if this array is empty then it means that first element is min, if not we do the same for the new array unless we reach an empty array. the recursion is provided by using the same function in the definition of the function.

CodePudding user response：

Solutions which in the worst case reduce the problem size by 1 will cause the recursive stack to have O(length(array)) growth. An example of this would be when you filter the array to yield values less than the first element when the array is in descending order. This will inevitably lead to stack overflow for sufficiently large arrays. To avoid this, you want to use a recursion which splits the problem of size n into two subproblems of size n/2, yielding O(log(length(array))).

I'm not a Matlab user/programmer, so I'll express the algorithm in pseudo-code. The following assumes that arrays are 1-based and that there is a built-in function min(a,b) which yields the minimum of two scalars, a and b. (If not, it's easy to replace min() with if/else logic.)

function min_element(ary) {
  if length(ary) == 1 {
    return ary[1]
  }
  split ary into first_half, second_half which differ in length by no more than 1
  return min( min_element(first_half), min_element(second_half) )
}

This could alternatively be written using two additional arguments for the lo_index and hi_index to search between. Calculate the midpoint as the integer average of the low and high indices, and make the two recursive calls min_element(ary, lo_index, mid) and min_element(ary, mid 1, hi_index). The base condition is when lo_index == hi_index, in which case you return that element. This should be faster, since it uses simple integer arithmetic and avoids creating sub-arrays for the subproblems. It has the trade-off of being slightly less friendly to the end user, who has to start the process by calling min_element(ary, 1, length(ary)).

If the stack limit is 500, you'll be limited to arrays of length < 500 using linear stack growth algorithms. With the divide-and-conquer algorithm described above, you won't get stack overflow unless you have an array of length ~2⁵⁰⁰, much bigger than any array you could actually create.