Recursive function to find median

I have a function as follows, intended to calculate the median using recursion (without any built in functions):

function [ val ] = findMedian( inputArray )
%UNTITLED4 Summary of this function goes here
%   Detailed explanation goes here
n=length(inputArray);
mid=ceil(n/2);
k=randi(1,n);
val=findTerm(inputArray,k);
function [ val ] = findTerm( inputArray,k )
  % recursive function
  % inputArray: a 1 by N unordered double array
  % k: integer between 1 and the length of inputArray
  % val: the k-th smallest term of inputArray
  % findTerm: randomly picks one term from inputArray; then,
  % searches recursively one of the three sub-arrays that contains
  % the k-th smallest term of inputArray

inputArray=inputArray(:); 
k=k-1; 

while (1)  

    x=randi(length(inputArray));
    val=x;
    a1=inputArray<val; 
    n1=sum(a1); 

    if inputArray<n1
        inputArray=inputArray(a1); 
    elseif k<(n1+sum(inputArray==val))
        break;
    else
        inputArray=inputArray(inputArray>val);
        k=k+numel(inputArray)-numel(a1); 
    end
end

end
end

However, when I sample this function using the command:

findMedian([1 2 3 4 5 6 7])

it produces 1 instead of the actual median 4. How do I change the while-loop to recursion?

Answer 1

[Guillaume]

Probably the most important thing is that your algorithm is not recursive. A recursive function is a function that calls itself.

In view of that finding out what is wrong with it is pretty much irrelevant. However, the best way for you to find out where it goes wrong is to step through your program and see how the variables evolve.

I'll note a few things:

• Use meaningful variable names instead of a1, k, n1. It's much easier to follow a program when the variable names are words that explain what's in them (e.g. your inputArray).
• There's no point in

x = somevalue;
val = x;
%... code that never use x

simply use

val = somevalue;  %and use a better name than val

• it's unlikely that your

if inputArray<n1

does what you want. The if will only be true if all elements of inputArray are smaller than n1. If that is indeed what you intended to do, then use

if all(inputArray < n1)

to remove the ambiguity.

edit: What sort of algorithm are you trying to implement?. Some small parts of your code look like a quickselect but the majority does not. In particular, for a quickselect, at some point, you need to do something with your mid variable that is currently completely unused.