Hump-day challenger - Recursion

조회 수: 2(최근 30일)
Matt Fig
Matt Fig 2011년 3월 2일
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!
  댓글 수: 7
Matt Fig
Matt Fig 2011년 3월 30일
Thanks to Kenneth and Jan for their submissions!

댓글을 달려면 로그인하십시오.

채택된 답변

Kenneth Eaton
Kenneth Eaton 2011년 3월 2일
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
  댓글 수: 1
Matt Fig
Matt Fig 2011년 3월 2일
Nice, Kenneth. Different than the one I posted, which is good!

댓글을 달려면 로그인하십시오.

추가 답변(7개)

Jan
Jan 2011년 3월 2일
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
Jan 2011년 3월 3일
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
Jan 2011년 3월 4일
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
Jan 2011년 3월 4일
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
Jan 2011년 3월 4일
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

Matt Fig
Matt Fig 2011년 3월 10일
O.k., here is my other idea. It first sorts the array then uses a much more efficient recursive method than the algorithm I posted to start this thing off. Note that if it is objected that I used SORT, I could have written a recursive sort algorithm too (perhaps the subject of another challenger)! (Does this get me off the hook?) In my timings, given the inputs I included in the challenge description, this is about 70 times faster.
function idx = recurse_find_s(A,V)
% Returns the location of value V in a vector of unique values.
% A is the array, V the value to find.
[A,I] = sort(A);
idx = I(find_array_sub(A,V,1,length(A)));
function idx = find_array_sub(A,V,L,R)
% Subfunction for recurse_find_s. Recursion ahead.
if L>R
idx = [];
else
M = floor((L+R) /2);
if V==A(M)
idx = M;
elseif V < A(M); % Recursive call.
idx = find_array_sub(A,V,L,M-1);
else
idx = find_array_sub(A,V,M+1,R);
end
end
  댓글 수: 1
Jan
Jan 2011년 3월 31일
Very nice and "actually obvious" (this means: "obvioulsy not obvious"). Creating a binary search tree reduces the recursion depth substantially. +1

댓글을 달려면 로그인하십시오.


Matt Fig
Matt Fig 2011년 3월 10일
O.k., here is something I do not understand. In trying to make the original algorithm I published (reproduced below) more efficient, I thought, "Why not use a nested function instead of a subfunction, that way we wouldn't have to pass around copies of the array." However, this is much slower! Can anyone explain why?
The original: .
.
function idx = recurse_find(A,V)
% Returns the location of value V in a vector of unique values.
% A is the array, V the value to find.
idx = find_array_sub(A,V,1,length(A));
function idx = find_array_sub(A,V,L,R)
% Subfunction for recurse_find. Recursion ahead.
if L>R
idx = [];
else
M = floor((L+R) /2);
if V==A(M)
idx = M;
else
idxat = find_array_sub(A,V,L,M-1); % Recursive call.
if ~isempty(idxat)
idx = idxat;
else
idx = find_array_sub(A,V,M+1,R) ; % Recursive call.
end
end
end
.
And the nested version of the same exact algorithm:
.
function idxn = recurse_find_n(A,V)
% Returns the location of value V in a vector of unique values.
% A is the array, V the value to find.
idxn = find_array_nest(1,length(A));
function idx = find_array_nest(L,R)
% Nested function, here is the recursion.
if L>R
idx = [];
else
M = floor((L+R) /2);
if V==A(M)
idx = M;
else
idxat = find_array_nest(L,M-1);
if ~isempty(idxat)
idx = idxat;
else
idx = find_array_nest(M+1,R) ;
end
end
end
end
end
  댓글 수: 1
Jan
Jan 2011년 3월 31일
Strange effect. I'd accuse the JIT to be too lazy inside a nested function. Passing copies of the arrays has the benefit, that there are no side effects.

댓글을 달려면 로그인하십시오.

Community Treasure Hunt

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

Start Hunting!

Translated by