该算法在这里如何工作？该函数在其自身内部被调用

Question

我试图弄清楚这个循环是如何工作的：

为什么m取值0时又调用了函数？不应该return0吗？

static void Main(string[] args)
    {
        Console.WriteLine(GridTraveler(3,2));
    }
    public static int GridTraveler(int m,int n)
    {
        if(m == 1 && n == 1) return 1;
        if(m == 0 || n == 0) return 0;
        return GridTraveler(m-1,n) + GridTraveler(m,n-1);
    }

Answer 1

这是一个递归函数。

这是归纳定义函数的直接翻译

gt(m,n) = gt(m-1,n) + g(m,n-1)  if (m,n) =/= (1,1) and (m =/= 0 and n =/= 0)
gt(1,1) = 1
gt(0,x) = 0 for all x
gt(x,0) = 0 for all x

这是 Prolog 中的一个，递归大师：

:- table gt/3.

gt(1,1,1) :- !.
gt(0,_,0) :- !.
gt(_,0,0) :- !.
gt(M,N,R) :- 
   Mm is M-1, 
   Nm is N-1, 
   gt(Mm,N,Ra), 
   gt(M,Nm,Rb), 
   R is Ra+Rb.

?- gt(10,10,R).
R = 48620.

或者，打印输出：

:- table gt/4.

gt(M,N,Result) :- gt(M,N,Result,0).

gt(1,1,1,Indent) :- !,format("~t~*|Reached (1,1)\n",[Indent]).
gt(0,X,0,Indent) :- !,format("~t~*|Reached (0,~q)\n",[Indent,X]).
gt(X,0,0,Indent) :- !,format("~t~*|Reached (~q,0)\n",[Indent,X]).
gt(M,N,R,Indent) :- 
   format("~t~*|Called for (~q,~q)\n",[Indent,M,N]),
   Mm is M-1, 
   Nm is N-1,
   Indentp is Indent+2, 
   gt(Mm,N,Ra,Indentp), 
   gt(M,Nm,Rb,Indentp), 
   R is Ra+Rb,
   format("~t~*|Result for (~q,~q) is ~q\n",[Indent,M,N,R]).

然后：

?- gt(3,3,R).
Called for (3,3)
  Called for (2,3)
    Called for (1,3)
      Reached (0,3)
      Called for (1,2)
        Reached (0,2)
        Reached (1,1)
      Result for (1,2) is 1
    Result for (1,3) is 1
    Called for (2,2)
      Called for (2,1)
        Reached (2,0)
      Result for (2,1) is 1
    Result for (2,2) is 2
  Result for (2,3) is 3
  Called for (3,2)
    Called for (3,1)
      Reached (3,0)
    Result for (3,1) is 1
  Result for (3,2) is 3
Result for (3,3) is 6
R = 6.

该算法在这里如何工作？该函数在其自身内部被调用

How does the algorithm work here? The function is called inside itself

function

dynamic-programming