how to fix ''Out of memory. The likely cause is an infinite recursion within the program. Error in rcca (line 12) rcca(nx,ny,A,k); ''

I am trying to using the Contour Tracing estimation algorithm but I have no idea about this error. the input file is D which is uploded in the attachments.

 function [detected_img] = Contour_Tracing_estimation_algorithm(D) 
A=~D;
% k indicates number of components in binary image
k = 0;
global B;
B = zeros(size(A,1),size(A,2));
% to make sure boundary conditions, skip first row, column and last row,
% column. These will be taken care by recursive function calls later
for i = 2 : size(A,1) - 1 
  for j = 2 : size(A,2) - 1
      if A(i,j) == 1 && B(i,j) == 0
          k = k + 1;
          rcca(i,j,A,k);
      end
  end
end
for i = 1 : size(A,1)
  if A(i,1) == 1 && B(i,1) == 0
      k = k + 1;
      B(i,1) = k;
  else
      if A(i,size(A,2)) == 1 && B(i,size(A,2)) == 0
          k = k + 1;
          B(i,size(A,2)) = k;
      end
  end
end
for j = 1 : size(A,2)
  if A(1,j) == 1 && B(1,j) == 0
      k = k + 1;
      B(1,j) = k;
  else
      if A(size(A,1),j) == 1 && B(size(A,1),j) == 0
          k = k + 1;
          B(size(A,1),j) = k;
      end
  end
end
Nof_SignalArea = k;
fprintf('\ntotal number of components in image = %.0f\n',k);
detected_img = ones(size(D,1), size(D,2));
for K= 1:Nof_SignalArea
[r, c] = find(B==K);
rc{K,:}= [r, c];
detected_img(r, c) = 0;
end
 end
 

this is a rcca(i,j,A,k) function

 function rcca(x,y,A,k)
global B;
B(x,y) = k;
% dx and dy is used to check for 8 - neighbourhood connectivity
dx = [-1,0,1,1,1,0,-1,-1];
dy = [1,1,1,0,-1,-1,-1,0];
if x > 1 && y > 1 && x < size(A,1) && y < size(A,2)
  for i = 1 : 8
      nx = x + dx(i);
      ny = y + dy(i);
      if A(nx,ny) == 1 && B(nx,ny) == 0
          rcca(nx,ny,A,k);
      end
  end
end

[Walter Roberson]

There are non-recursive contour tracing algorithms (or, in your case, really edge tracing rather than contour) that would probably be better for your purpose.

Answer 1

[Aghamarsh Varanasi]

Hi,

You are trying to implement the contour algorithm on the matrix. As the algorithm that you provided ( rcca ) is recursive, the number of function calls may increase significantly.

function rcca(x,y,A,k)
    ...
    rcca(nx,ny,A,k);
    ...
end 

Recursive algorithms use the recursion stack space to maintain the function call records. When the number of recursive function calls increase, the recursion stack is used up and you will end up exhausting it. This is the actual reason for the error that you get.

This error indicates that there might be any design error, so try decreasing the recursion levels and optimizing the code by dividing the task in slices and apply the recursive algorithm to these slices.

[Mohammed Alammar]

Thank you all, I still have confused because this code working when I have reduced the size of D matrix. However, when D size more than 500*500 it show this error. could you please guide me

[Steven Lord]

If you were to sing the song "99 Bottles of Beer" it might take you thirteen and a half minutes (the Wikipedia page says that's been done.)

If you were to try to sing the variant "1,000,000 Bottles of Beer" you're not going to be able to do it in one sitting.

The song is recursive and has a termination condition (0 bottles of beer on the wall.) Your function is recursive and doesn't have a termination condition.

You're not able to run your algorithm on problems of size greater than 500. In part that's because we impose a recursion limit, to prevent the stack space exhaustion Aghamarsh Varanasi mentioned. Exhausting the stack space could crash MATLAB. If you really want to try you could increase the recursion limit, as I believe the error message indicates, but you may risk your MATLAB session (or your computer) crashing.

If I understand what you're trying to do correctly, you're trying to identify connected components. Is that correct? If so and you have Image Processing Toolbox I believe bwconncomp will do what you want.

If you have to implement this yourself, identify your termination condition. When will rcca not call itself?

[Walter Roberson]

Hmmm, I would call 99 Bottles of Beer an iterative process rather than a recursive process.

Recursive process for obtaining the current last bottle of beer on the wall:

1) take down all of the bottles of beer on the wall into your hands and start the "last bottle" process with
everything in your hand
2) Last bottle process applied to bottles of beer in hand:
   2a) if you only have one bottle of beer in hand, it is the last bottle
       and return it to whoever you got it from
   2b) otherwise, remove the first bottle of beer and put it back on the wall
       at the end, and hand the rest to the next person to apply the last bottle
       process to
   2c) when that person eventually hands you back a bottle, return it to whoever
       you received the collection of bottles from

Each step is working with a smaller and smaller problem (passing fewer and fewer bottles around), and eventually the last bottle is obtained and is passed back through the chain of people until there are no more steps in the chain and that bottle is the solution to "fetch the last bottle".

Answer 2

[Walter Roberson]

Recursive functions should never assign into global variables (except perhaps counting the calls) and should always return the results (except in cases where the calls are being made for their side effects such as plotting or writing to file).

Recursion always needs a termination condition.

In most cases, recursive calls should do some work and then call the function on a problem that is in some way "smaller" and incorporate the results returned. With it being a smaller problem in the call, by induction you would get down to a problem trivially solved (the termination condition). It is, however, also valid to formulate the code in terms of testing the termination first, then calling recursively on the smaller problem, then doing the work. Consider the difference between

function f = factorial(n)
  if n<=1; f = 1; else f = factorial(n-1)*n; end

And

function f = factorial(n)
  if n<=1; f = 1; else f=n*factorial(n-1); end

clearly both are equivalent mathematically, but they potentially have different low level implementations.

[Mohammed Alammar]

Thank you all, I still have confused because this code working when I have reduced the size of D matrix. However, when D size more than 500*500 it show this error. could you please guide me