How should you approach recursion?

Question

I am currently studying recursion in school, and I have trouble thinking about methods when there are many recursive calls. I just want to ask how you should think about recursion because I know tracing the method calls by each step will become too tedious.

Instead of tracing each recursive call, the thing we briefly covered was thinking about recursion by induction, but the problem I have is seeing how induction can be applied to situations other than math. Like if there is a method that recursively prints out numbers like this:

public void blah(int n)
{
    for (int i = 0; i < n; i++)
      blah(i);
    System.out.print(n);
}

I have trouble thinking about what prints out, and I can't see how induction could be relevant here (pardon my ignorance if it can be used everywhere).

But I guess my real question is how you can tackle recursion without having to trace every single method call? Is the best thing to do just to see the base case and sort of work backwards? (But even then I think I get fuzzy about what happens).

Answer 1

You can find a nice explanation about Thinking Recursively over here

From the link

• Write a prototype for the recursive function.

• Write a comment that describes what the function does.

• Determine the base case (there may be more than one), and its solution(s).

• Determine what smaller problem (or problems) to solve. If it makes it easier for you to follow, save the solutions to the smaller
  problems to local variables (e.g., small in the sum() example).ASSUME the recursive call works

• Use the solutions of the smaller problem to solve the larger problem. (If this is done INCORRECTLY, the solutions of the smaller
  problems will also be computed incorrectly, thus, the assumption in
  the previous step will fail).