Recursion tracing help

[akshitha Akki]

class Anaram {
	public void printAnagrams(String prefix, String word)
	{
		if(word.length() <= 1)
		{
			System.out.println(prefix + word);
			System.out.println("after single character ========================================");
		} 
		else
		{
			for(int i = 0; i < word.length(); i++)
			{
				String cur = word.substring(i, i + 1);
				System.out.println(cur);
				String before = word.substring(0, i); // letters before cur
				System.out.println(before);
				String after = word.substring(i + 1); // letters after cur
				System.out.println(after);
				System.out.println(":::::::::::::::::::::");
				printAnagrams(prefix + cur, before + after);
				
				System.out.println("after loop ++++++++++++"  + i);
			}
		}
	}
}

public class Ana
{
	public static void main(String args[])
	{
		Anaram obj = new Anaram();
		obj.printAnagrams("", "goat");
	}
}

Can anyone help me in tracing the recursion program?

[Jeff Verdegan]

It's hard to offer help when you don't ask a more specific question.

However, in general what you can do to help follow the recursion is to include an indication of how deep you are.

For example:

// before
int fact(int n) {
  int result;

  if (n == 0) {
    result = 1;
  }
  else {
    result = n * fact(n - 1);
  }

  return result;
}



// after
int fact(int n) {
  return fact(n, 1)
}

int fact(int n, int depth) {
  for (int i = 0; i < depth; i++) {
    System.out.print(".");
  }
  System.out.println("starting (" + n + ", " + depth + ")");

  int result;

  if (n == 0) {
    result = 1;
  }
  else {
    result = n * fact(n - 1, depth + 1);
  }

  
  for (int i = 0; i < depth; i++) {
    System.out.print(".");
  }
  System.out.println("returning " + result + " (" + n + ", " + depth + ")");
  return result;
}

And then of course adding or changing the output to show you whatever you're not understanding.

[akshitha Akki]

Thanks Jeff. The way to trace a program you have provided helped me a lot.I also did a hand trace as well to get more clarity.

[Jeff Verdegan]

Yes, a hand trace is always advisable. It can get messy fast in the case of recursion though. That's where the printouts come in.