How does a recursive function inside a while loop works in Java?

Question

I found this code on google but i couldn't find how does the recursive part actually work. The code is about finding the possible path between 2 vertices on a directed graph. Here is the method to print the total possible path :

public void  total_path(int source, int destination)
{
  result = 0;
  boolean[] visit = new boolean[size];
  for(int i = 0; i < size; i++)
  {
    visit[i] = false;
  }
  count_path(source, destination, visit);
  System.out.println(result);
}

Here is the recursive method to count all possible paths :

  public void  count_path(int start, int end, boolean[] visit)
     {
              if(start > size || end > size || start < 0 || end < 0 || node == null)
              {
                return ;
              }
        
              if(visit[start]==true)
              {
                return;
              }
        
              if(start == end)
              {
                 result = result + 1;
              }
              
              visit[start] = true;
              AjlistNode temp = node[start].next;
        
              while(temp!=null)
              {
                count_path(temp.id, end, visit); 
                temp = temp.next;
              }
              
              visit[start]=false;
     }

Here is the graph which i created :

g.addEdge(0, 1); 
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 5);
g.addEdge(3, 4);
g.addEdge(4, 2);
g.addEdge(4, 5);
g.addEdge(5, 6);

I already compiled and run the program which start point is 0 and end point is 6. The result is 3, already looked up on YouTube about the algorithm but i still can't understand on how to visualize and how does the code flow on the recursion part inside a while loop.

thank you so much! it really helps me a lot more in understanding the problem — Hasbiallah Al Amin
– Hasbiallah Al Amin, Commented Dec 11, 2021 at 1:54
How about you show your appreciation by upvoting and tagging my answer as the correct one? ;) — hfontanez
– hfontanez, Commented Dec 11, 2021 at 3:51
Don't forget to click the gray checkmark under the voting arrow :) — hfontanez
– hfontanez, Commented Dec 11, 2021 at 4:04

hfontanez · Accepted Answer · 2021-12-10 18:59:47Z

1

A recursive function must contain a base case to return a value rather than the result of the recursive call. In this case:

if(start > size || end > size || start < 0 || end < 0 || node == null)
{
    return;
}
    
if(visit[start]==true)
{
    return;
}

are those base cases that will break the recursive call chain. Remember, the method count_path returns void. If the method needed to return some value, you would've seen those if blocks returning some kind of default value. For instance, when you see examples of recursive Fibonacci, the base cases for Fib(0) and Fib(1) return the input value. Otherwise, it returns the result of the (cumulative) recursive call.

What are these base cases?

The method calculate the number of paths to some destination node from the current node. Therefore, if the node was already visited (and thus the paths should've been calculated already) simply return without recalculating. Also, if you have just one node in your graph, or no nodes, then there are no paths (so return without calculation).

Why is the answer 3 paths?

The picture below is based on the calls made to add edges. Each entry is a unidirectional path from a starting node to an ending node. So, starting at Node 0, to get to Node 6, there are three paths and they are outlined in the attached picture.

enter image description here

edited Dec 10, 2021 at 18:59

answered Dec 10, 2021 at 16:49

hfontanez

6,2082 gold badges29 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Hasbiallah Al Amin Over a year ago

I see, so in my case, what should the return value be?

hfontanez Over a year ago

@HasbiallahAlAmin draw them on a piece of paper and do the work by hand. Then, compare your drawing with the code. I am assuming the code is correct. At any rate, I think I answered your original question. If I have, please mark this question as such and upvote my answer.

Collectives™ on Stack Overflow

How does a recursive function inside a while loop works in Java?

1 Answer 1

What are these base cases?

Why is the answer 3 paths?

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

What are these base cases?

Why is the answer 3 paths?

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related