Why doesn't this code have a recursion error?

Question

Richard McCulloch 2016-5-1

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/282035-why-doesn-t-this-code-have-a-recursion-error

评论： Richard McCulloch 2016-5-2

There is a link to a Matlab sudoku solver here: Matlab Sudoku Solver (shown below). I wrote my own solver (shown below) and I get "recursion error" when it runs. It's basically the exact same thing with different variable names. Why does my code get a recursion error while the code in the link doesn't? Thanks!

Matlab Code

function X = sudoku(X) 
% SUDOKU  Solve Sudoku using recursive backtracking. 
%   sudoku(X), expects a 9-by-9 array X. 
 % Fill in all “singletons”. 
 % C is a cell array of candidate vectors for each cell. 
 % s is the first cell, if any, with one candidate. 
 % e is the first cell, if any, with no candidates. 
 [C,s,e] = candidates(X); 
 while ~isempty(s) && isempty(e) 
    X(s) = C{s}; 
    [C,s,e] = candidates(X); 
 end 
 % Return for impossible puzzles. 
 if ~isempty(e) 
    return 
 end 
 % Recursive backtracking. 
 if any(X(:) == 0) 
    Y = X; 
    z = find(X(:) == 0,1);    % The first unfilled cell. 
    for r = [C{z}]            % Iterate over candidates. 
       X = Y; 
       X(z) = r;              % Insert a tentative value. 
       X = sudoku(X);         % Recursive call. 
       if all(X(:) > 0)       % Found a solution. 
          return 
       end 
     end 
   end 
% ------------------------------ 
   function [C,s,e] = candidates(X) 
      C = cell(9,9); 
      tri = @(k) 3*ceil(k/3-1) + (1:3); 
      for j = 1:9 
         for i = 1:9 
            if X(i,j)==0 
               z = 1:9; 
               z(nonzeros(X(i,:))) = 0; 
               z(nonzeros(X(:,j))) = 0; 
               z(nonzeros(X(tri(i),tri(j)))) = 0; 
               C{i,j} = nonzeros(z)’; 
            end 
         end 
      end 
 L = cellfun(@length,C);   % Number of candidates. 
 s = find(X==0 & L==1,1); 
 e = find(X==0 & L==0,1); 
 end % candidates 
end % sudoku

My Code

function X=SD(X)
    % C is a cell array of candidate vectors for each cell.
    % s is the first cell, if any, with one candidate.
    % e is the first cell, if any, with no candidates.
    [C,s,e] = candidate(X);
    while ~isempty(s) && isempty(e)
        X(s) = C{s};
        [C,s,e] = candidate(X);
    end
      % Return for impossible puzzles.
      if ~isempty(e)
          return
      end
      % Recursive Backtracking
      if any(X(:) > 0)
          Y=X;
          [row,col]=find(X==0,1,'first');
          for k=1:length(C{col,row})
              X=Y;
              X(col,row)=C{col,row}(k);
              X=SD(X);
              if all(X(:)>0)
                  return
              end
          end
      end
      function [C,s,e]=candidate(X)    
          C=cell(9,9);
          for j=1:9
              for i=1:9
                  % remove numbers already in current row/column
                  p=1:9;
                  t1=nonzeros(X(j,:));
                  t2=nonzeros(X(:,i));
                  % remove numbers already in current minor matrix
                  t3=nonzeros(X(3*ceil(j/3)-2:3*ceil(j/3),3*ceil(i/3)-2:3*ceil(i/3)));
                  p(nonzeros([t1' t2' t3']))=0;
                  C{j,i}=nonzeros(p);
              end
          end
          L = cellfun(@length,C);   
          s = find(X==0 & L==1,1);
          e = find(X==0 & L==0,1);
      end
  end

2 个评论
显示无隐藏无

John D'Errico 2016-5-1

编辑：John D'Errico 2016-5-1

Maybe this should teach you not to take code from someone else, change the variable names, and without even bothering to understand the code, hope to hand it in for your homework assignment. Karma.

Richard McCulloch 2016-5-2

I'm not in school. This is merely for my own amusement. I understand the sentiment, but it is misplaced.

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Stephen23 2016-5-2

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/282035-why-doesn-t-this-code-have-a-recursion-error#answer_220350

在 MATLAB Online 中打开

You changed this:

if any(X(:) == 0)

into this:

if any(X(:) > 0)

Think about it.

PS: MATLAB includes a Comparison tool which is very useful to track down problems like this.

3 个评论
显示 1更早的评论隐藏 1更早的评论

Stephen23 2016-5-2

编辑：Stephen23 2016-5-2

在 MATLAB Online 中打开

Simply calling a function is not the definition of recursion: it is the depth of recursion that matters (for the limit). So clearly you are calling your function lots of times, but without recursion to 500 calls deep.

fun1a
     fun2a
          fun3a
     fun2b
          fun3b
          fun3c
     fun2c
          etc

See: lots of calls, but only depth of three. This is what recursion means. To check the recursion depth you could add a depth variable to the function input and output, and keep track of that.

Richard McCulloch 2016-5-2