Program to calculate total paths in a maze from (0,0) to (n,m)-CodePudding

I am a newbie to the concept of recursion. Following is the code that calculates the total number of paths that can be taken for going from (0,0) to (n,m). The rule for reaching the final position is that we can move only right or downwards. I am unable to understand how recursion is working here.

I tried to understand it by using print statements but couldn't understand what is happening after 3rd call to ``rightPath```.

public class Main{
  public static int countPaths(int i, int j, int n, int m){
      if(i==n || j==m){
          return 0;
      }
      if(i==n-1 && j==m-1){
          return 1;
      }
      int downPath = countPaths(i 1, j, n, m);
      int rightPath = countPaths(i, j 1, n, m);
      return downPath   rightPath;
  }
  public static void main(String[] args){
      int n = 3, m = 3;
      int totalPaths = countPaths(0, 0, n, m);
      System.out.println(totalPaths);
  }
}

Please anybody explain me how the recursion is working here.

CodePudding user response：

Not sure, but maybe this can help you:

countPaths(0, 0, 3, 3) // (0, 0)
    = countPaths(0   1, 0, 3, 3) // (1, 0)
        = countPaths(1   1, 0, 3, 3) // (2, 0)
          countPaths(1, 0   1, 3, 3) // (1, 1)
            [...]
      countPaths(0, 0   1, 3, 3) // (0, 1)
        = countPaths(0   1, 1, 3, 3) // (1, 1)
          countPaths(0, 1   1, 3, 3) // (0, 2)
            [...]

It aims to show you how the function is nested executed and which values are calculated and returned.

CodePudding user response：

Your "countPaths" function is called two times recursively at each step. In this case you have 2 BASE conditions, with the role of stopping the recursive function from executing endlessly (that are your two IF statements).
At each execution, 2 new nested call (D AND R) (path) are created incrementing i or j ... unless one of the condition is reached. The total path is then calculated using the sum of the returning value.
Like this: