Why recursion in java is so slow compared to .net?
<p>I wrote an algorithm to find all the paths possible between two points. i wrote the algorithm in both c#.net and java. The algorithm produces around 40,000 possible paths. To my amazement the algorithm in C#.net took only 13 mins to complete (in i3 processor), while java could not complete even in 4 hrs.</p>

<p>recursion may be slow in java , but i don't think this much.</p>

<p>Is there anything i am missing ?</p>

<p>Ok here is the requirement , a maze is a two dimensional array which contains numbers 0,1,2 and 3. 0 represents the walkable points, 1 represents the obstacle , 2 the starting point and 3 the exit point. the program was to find all the paths from point 2 to 3 by touching all 0s only one time. we cannot step over 1s as they are obstacles.</p>

<h2>here is the code in C#.Net</h2>

<pre><code>public class Maze
{
    //Represents each point in the Maze.
    private class Node
    {
        private int val;

        public Node(int num)
        {
            val = num;

            switch (num)
            {
                case 1: IsPit = true;
                    break;
                case 2: IsEntranceNode = true;
                    break;
                case 3:
                    IsExitNode = true;
                    break;
            }
        }
        public string Name { get; set; }

        public bool IsPit { get; private set; }
        public bool IsVisited { get; set; }
        public bool IsExitNode { get; private set; }
        public bool IsEntranceNode { get; private set; }

        public Node UpNode { get; set; }
        public Node DownNode { get; set; }
        public Node LeftNode { get; set; }
        public Node RightNode { get; set; }
    }

    #endregion

    //Number of pits in the maze.
    private int numberOfPits;

    //Stack traces the path traversed.
    private Stack&lt;String&gt; pathTraversed;

    //Represents the maze.All Nodes are wired to its adjacent nodes.
    private Node[,] Maze { get; set; }

    //Number of paths found.
    private int pathCount = 1;

    //displays a set.
    static void printSet(int[,] set)
    {
        Console.Write(" \t");
        for (var i = 0; i &lt; set.GetLength(1); i++)
            Console.Write(i + "  ");

        Console.WriteLine("\n--------------------------");

        for (var i = 0; i &lt; set.GetLength(0); i++)
        {
            Console.Write((char)(65 + i) + " | \t");
            for (var j = 0; j &lt; set.GetLength(1); j++)
                Console.Write(set[i, j] + "  ");

            Console.WriteLine();
        }
    }

    static void Main(string[] args)
    {
        int[,] set2 = new int[7, 7] {   { 2, 0, 0, 0, 0, 0, 0 }, 
                                        { 0, 0, 0, 0, 0, 0, 0 }, 
                                        { 0, 0, 0, 0, 0, 0, 0 }, 
                                        { 0, 0, 0, 0, 0, 0, 0 }, 
                                        { 0, 0, 0, 0, 0, 0, 0 }, 
                                        { 0, 0, 0, 0, 0, 0, 0 }, 
                                        { 0, 0, 0, 0, 3, 1, 1 } 
                                    };          

        Console.WriteLine("\n\nSet 2");
        Console.WriteLine("=====");
        printSet(set2);

        Console.WriteLine("\nPath found");
        Console.WriteLine("==========");
        startTime = DateTime.Now;
        new Maze().AddPoints(set2).FindPaths();
        endTime = DateTime.Now;
        difference = endTime.Subtract(startTime).TotalMinutes;
        Console.WriteLine("Time taken in mins : " + difference);
        Console.WriteLine("\nPress any key to exit");
        Console.ReadKey();
    }

    //Adds points to the maze.Transforms a matrix to 2 dimensional connected nodes.
    public Program AddPoints(int[,] matrix)
    {
        Maze = new Node[matrix.GetLength(0), matrix.GetLength(1)];

        for (int i = 0; i &lt; matrix.GetLength(0); i++)
        {
            for (var j = 0; j &lt; matrix.GetLength(1); j++)
            {
                Node node = Maze[i, j];

                if (node == null)
                {
                    node = new Node(matrix[i, j]);
                    Maze[i, j] = node;
                }
                if (!(i - 1 &lt; 0))
                    Maze[i - 1, j].DownNode = node;

                if (!(i + 1 &gt; matrix.GetLength(0) - 1))
                {
                    var downNode = Maze[i + 1, j];
                    if (downNode == null)
                        Maze[i + 1, j] = new Node(matrix[i + 1, j]);
                    Maze[i + 1, j].UpNode = node;
                }

                if (!(j - 1 &lt; 0))
                    Maze[i, j - 1].RightNode = node;

                if (!(j + 1 &gt; matrix.GetLength(1) - 1))
                {
                    var leftNode = Maze[i, j + 1];
                    if (leftNode == null)
                        Maze[i, j + 1] = new Node(matrix[i, j + 1]);
                    Maze[i, j + 1].LeftNode = node;
                }

                node.Name = ((char)(65 + i)).ToString() + j.ToString();
                if (node.IsPit)
                    numberOfPits++;
            }
        }
        return this;
    }

    //Finds path between the start node and end node.
    public void FindPaths()
    {
        var startNode = Maze[0, 0];

        if (!startNode.IsEntranceNode)
            throw new Exception("Node is not starting node.");

        pathTraversed = new Stack&lt;string&gt;();

        pathTraversed.Push(startNode.Name);
        Traverse(startNode.RightNode);
        Traverse(startNode.DownNode);
        Traverse(startNode.LeftNode);
        Traverse(startNode.UpNode);
    }

    //Traverses a node.
    private void Traverse(Node node)
    {
        if (node == null)
            return;

        if (node.IsEntranceNode || node.IsPit || node.IsVisited)
            return;

        if (node.IsExitNode)
        {
            pathTraversed.Push(node.Name);
            if (pathTraversed.Count == Maze.Length - numberOfPits)
            {
                var msg = "Path " + pathCount++ + " : " + string.Join("-&gt;", pathTraversed.Reverse());
                Console.WriteLine(msg);
            }
            pathTraversed.Pop();
            return;
        }

        pathTraversed.Push(node.Name);
        node.IsVisited = true;

        Traverse(node.RightNode);   //
        Traverse(node.DownNode);    // Move to Next Node
        Traverse(node.LeftNode);    //  
        Traverse(node.UpNode);      //

        if (node.Name != pathTraversed.Peek())
            throw new Exception("Error in Logic.");

        node.IsVisited = false;
        pathTraversed.Pop();
    }
}
</code></pre>

<h2>and here is the program in Java</h2>

<pre><code>public class PathFinder
{
  public static void main(String[] args){
    int[][] set1 = new int[][] { { 2, 0, 0, 0, 0, 0, 0 }, 
            { 0, 0, 0, 0, 0, 0, 0 }, 
            { 0, 0, 0, 0, 0, 0, 0 }, 
            { 0, 0, 0, 0, 0, 0, 0 }, 
            { 0, 0, 0, 0, 0, 0, 0 }, 
            { 0, 0, 0, 0, 0, 0, 0 }, 
            { 0, 0, 0, 0, 3, 1, 1 }};
    ObservableStack&lt;String&gt; observableStack = new ObservableStack&lt;String&gt;();
    StackObserver stackObserver = new StackObserver(plotter);
    Maze maze = new Maze(set1,(IPathFinderStack&lt;String&gt;)observableStack);
    maze.findPaths();                   
  }
}

public class Maze {

private Node[][] nodes;

IPathFinderStack&lt;String&gt; pathTraversed;

private int numberOfPits = 0;

private  int result = 0;

public  Node[][] getVector(){
    return nodes;
}

public Maze(int[][] matrix ,IPathFinderStack&lt;String&gt; stack){
    pathTraversed = stack;
    addNodes(matrix);
}   

public void addNodes(int[][] matrix)    {

    int rows = matrix.length;
    int cols = matrix[0].length;

    nodes = new Node[rows][cols];

    for (int i = 0; i &lt; rows; i++)
    {
        for (int j = 0; j &lt; cols; j++)
        {
            Node node = nodes[i][j];

            if (node == null){
                node = new Node(matrix[i][j]);
                nodes[i][j] = node;
            }

            if (!(i - 1 &lt; 0))
                nodes[i-1][j].setDownNode(node);

            if (!((i + 1) &gt; rows - 1))
            {
                Node downNode = nodes[i+1][j];
                if (downNode == null)
                    nodes[i + 1][j] = new Node(matrix[i+1][j]);
                nodes[i + 1][j].setUpNode(node);
            }

            if (!(j - 1  &lt; 0))
                nodes[i][j-1].setRightNode(node);

            if (!(j + 1 &gt; cols - 1)){
                Node leftNode = nodes[i][j+1];
                if (leftNode == null)
                    nodes[i][j+1] = new Node(matrix[i][j+1]);
                nodes[i][j+1].setLeftNode(node);
            }

            String name =  new String(new char[] {(char) (65 + i), (char)(48 + j)});

            node.setName(name);

            if (node.isPit())
                this.numberOfPits ++;
        }
    }
}

public void findPaths(){    

    Node startNode = nodes[0][0];

    pathTraversed.push(startNode.getName());

    Traverse(startNode.getRightNode());
    Traverse(startNode.getDownNode());
    Traverse(startNode.getLeftNode());
    Traverse(startNode.getUpNode());
}   

private void Traverse(Node node){   

        if (node == null)
            return ;

    if (node.isEntrance() || node.isVisited() || node.isPit())
        return ;

    if (node.isExit()){

            pathTraversed.push(node.getName());
        if (pathTraversed.getLength() == (nodes[0].length * nodes.length) - numberOfPits){
            String msg = "Path found" + (++result);
            Logger.Log(msg);
            Logger.Log(pathTraversed.toString());
        }

        pathTraversed.pop();
        return;             
    }

    pathTraversed.push(node.getName());
    node.setVisited(true);

    Traverse(node.getRightNode());
    Traverse(node.getDownNode());
    Traverse(node.getLeftNode());
    Traverse(node.getUpNode());

    node.setVisited(false);
    pathTraversed.pop();        
}
}

public class Node
{
private String name;
private int val;
private boolean isPit;
private boolean isVisited;
private boolean isEntrance;
private boolean isExit;

private Node downNode;
private Node upNode;
private Node leftNode;
private Node rightNode;

public Node(int val){
    this.val = val;
    this.isPit = (val == 1);
    this.isEntrance = (val == 2);
    this.isExit = (val == 3);
    this.isVisited = false;         
}

public String getName(){
    return this.name;
}

public void setName (String name) {
    this.name = name;
}

public boolean isPit(){
    return isPit;
}

public boolean isVisited(){
    return isVisited;
}

public void setVisited(boolean isVisited)   {
    this.isVisited = isVisited;
}

public boolean isEntrance(){
    return isEntrance;
}

public boolean isExit(){
    return isExit;
}

public Node getDownNode(){
    return downNode;
}

public void setDownNode(Node node){
    downNode = node;
}

public Node getUpNode(){
    return upNode;
}

public  void setUpNode(Node node){
    upNode = node;
}

public Node getLeftNode(){
    return leftNode;
}

public void setLeftNode(Node node){
    leftNode = node;
}

public Node getRightNode(){
    return rightNode;
}   

public void setRightNode(Node node) {
    rightNode = node;
}
}   
</code></pre>

<p>the ObservableStack is a normal stack made of array. i made it observable to connect it to applet to animate the traversal.</p>

<p>I hope i have provided enough detail.</p>
