6 views (last 30 days)

Show older comments

In honor of John D'Errico (and some recent posts about recursion in MATLAB), I bring a recursion challenger.

Here is the challenge: Create a function which uses recursion to find the index location of one number in a vector of unique numbers. Your function should take a vector, and use recursion to find the index location of a value in the vector. The function should take both of the below values as arguments. The function should not call any built-in MATLAB set functions, including:

ISMEMBER, INTERSECT, SETDIFF, UNIQUE, UNION, SETXOR.

Also, no calls to FIND or toolbox functions!

M = randperm(10^4); % The vector of unique numbers.

V = ceil(rand*10^4) + 1; % The value to find.

As you can see, the value V might not be in M. In this case your function should return an empty array. Remember, you must use recursion to do the work! And no fair increasing the recursion limit beyond 500!

Here is one solution to the problem, lets see how others do it!

Kenneth Eaton
on 2 Mar 2011

My first attempt:

function index = find_index(M,V)

switch numel(M)

case 0

index = [];

case 1

if M == V

index = 1;

else

index = [];

end

otherwise

nHalf = ceil(numel(M)/2);

index = find_index(M(1:nHalf),V);

if isempty(index)

index = nHalf+find_index(M((nHalf+1):end),V);

end

end

end

Jan
on 2 Mar 2011

Kenneth's solution can be slightly modified to save memory:

function index = find_index(M, V, low, high)

if nargin == 2

low = 1;

high = length(M);

end

Len = high - low + 1;

switch Len

case 0

index = [];

case 1

if M(high) == V % or M(low)

index = high;

else

index = [];

end

otherwise

nHalf = ceil(Len / 2);

index = find_index(M, V, 1, nHalf);

if isempty(index)

index = find_index(M, V, nHalf + 1, high);

end

end

end

This cannot be called a new solution, but it was too ugly to post this without formatting in a comment. The underlying idea helps to avoid a common pitfall in recursive programming: wild data copy.

Jan
on 3 Mar 2011

I admit one can discuss if a nested R(R(R(R(...)))) call is a "recursion" in the strict formal definition. It seems to satisfy the definition on Wikipedia. And it does not collide with Matlab RecursionLimit.

Unfortunately this program does not run in modern Matlab versions, which restrict the levels of nested parenthesis to 32, but in Matlab 6.5 this runs:

function Index = FindIndex % Main function ---

N = 1e4;

M = randperm(N);

V = ceil(rand * N) + 1;

K = (V == M);

Data = [1, N+1, K]; % Need a single data vector

if any(K)

s1(2:2:2*N) = '('; % No REPMAT !

s1(1:2:2*N) = 'R';

s2(1:N) = ')';

Data = eval([s1, 'Data', s2]);

Index = Data(2);

else

Index = [];

end

function Data = R(Data) % Recursive subfunction: ---

if Data(1) % Not found before

Data(2) = Data(2) - 1;

if Data(2 + Data(2))

Data(1) = 0;

end

end

Jan
on 4 Mar 2011

If SPRINTF, SYSTEM and SAVE are accepted:

function R(M, V)

N = length(M);

if N == 0

N = [];

save('Result.mat', 'N');

else

if M(end) == V

save('Result.mat', 'N');

else

Cmd = ['R([', sprintf('%g ', M(1:end-1)), '], ', ...

sprintf('%g', V), ')'];

system(['matlab -r "', Cmd, '"']);

end

end

quit;

Again a discussion is possible, if this is a valid recursion. But if you look inside the stack trace, even a standard call of an M-function starts a new instance of m_interpreter.dll -> _inInterPCode.

Jan
on 4 Mar 2011

Because the vertical recursion would reach the RecursionLimit, we can split the numbers horizontally:

function Index = R2(M, V)

M(rem(M, 10) ~= rem(V, 10)) = -1;

match = (M >= 0);

if any(match)

if sum(match) == 1 && V < 10

K = 1:length(M);

Index = K(match);

else

M(match) = round(M(match) / 10);

Index = R2(M, round(V / 10));

end

else % No matching element:

Index = [];

end

This function compares the rightmost digit and sets not matching values to -1. The depth of recursion is limited to LOG10(max(M)). An equivalent approach prints the values to a CHAR matrix at first and crops the righmost caracter in each recursion.

Jan
on 4 Mar 2011

Flush the recursion at a certain level of recursion (< RecursionLimit, here: 100) and restart it:

function Index = FindIndex(M, V)

Index = R3(M, V, 0, 0);

% --- Recursive function: ---

function [Index, Found] = R3(M, V, Index, Level)

Index = Index + 1;

if Index > length(M) % Last element reached:

Index = [];

Found = 1;

elseif M(Index) == V % Matching element found:

Found = 1;

elseif Level < 100 % Call recursion

[Index, Found] = R3(M, V, Index, Level + 1);

if Found == 0 % Recursive call not successful:

if Level == 0 % Restart recursion in base level only:

[Index, Found] = R3(M, V, Index, 0);

end

end

else % Recursion limit reached:

Found = 0;

end

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!