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).

Answer 2

Here's the way I think about recursion. It's pretty simple, actually.

• What do I need to do in order to stop? This is known as your base case.
• What do I do if I'm not done yet?

Take, for example, the classical recursive problem: F(n) = n!. 0! is defined to be 1, and anything else greater than 0 is defined to be n*F(n-1)

In this example, I meet my two conditions - I stop when I hit 0!, and I multiply whatever value I have by the (n-1)th value.

Another approach I use: if it can be done recursively, then it can be done iteratively. This is to say, if I can write a loop to perform the same task, then I can write a recursive method to perform the task as well. It is often easier to think of certain problems recursively (e.g. Ackermann's Function), and others iteratively (e.g. walking down a linked list).

You would want to use iteration where it suits you best.

Answer 3

how you can tackle recursion without having to trace every single method call?

There are several ways of "understanding" recursive programs - one involves thinking of a recursive call as a black box, and the other requires "playing out" a few cases and guessing the pattern.

The first method assumes that the recursive method is already written, and that it does some known thing. This is useful when you think of recursive descent parsers; it is not that good for programs that produce output (as opposed to consuming input), such as yours.

The second method is more applicable to programs similar to your example. Play it out for values 0, 1, 2, and 3.

0 - 0
1 - 0 1
2 - 0 0 1 2
3 - 0 0 1 0 0 1 2 3

Did you notice the pattern? The output for N lists outputs for N-1 prior items, and prints N at the end. Once you think that you can continue the pattern, you know that you have an understanding of your recursive program.

Answer 4

Your example will print out

0 0 1 0 0 1 2 0 0 1 0 0 1 2 3 4

If called with blah(4).

In general when recursing I make sure to handle the base case first. After that, handle the state of the recursion, then the logic can come.

In this example, the base case control is i < n and will occur first at 0 < 0 which is untrue and breaks the for loop printing out 0. Then the next iteration out will run, which was to go from i = 0 to 1 < 1 which again prints out 0 after calling i = 0 < 0. Then it finishes the loop and the 1 is printed. Then it is 2s turn, lol. And so on down the line back out until each number has had it's turn.

Answer 5

Not sure exactly how to tell you to think of it but I think this might help you to grasp what the flow looks like. You get a feel for it after you code it for a while, but a lot of people just avoid it because it makes them feel icky. I apologize that it isnt coded in Java, but its not about the code its about what it prints so just run it on any Linux box or cygwin.

 perl -e 'sub foo {my $n =shift;my $depth=shift;print "\t"x$depth;print "blah($n)\n";for(my $i=0;$i<$n;$i++){foo($i,$depth+1)};print "\t"x$depth;print $n,"\n"};foo(shift);'  5

Called with an arg of 3 this is what it looks like:

    blah(3)
            blah(0)
            0
            blah(1)
                    blah(0)
                    0
            1
            blah(2)
                    blah(0)
                    0
                    blah(1)
                            blah(0)
                            0
                    1
            2
    3

I try like someone else said to visualize it in smaller components. I.E. What is the function doing besides the recursion. In this case the function is counting from 0 to some number. Now factor in what the recursion does. For each count it starts a new count up to the number it has reached. Often I find that it helps to break it up into more than one function such that the what it really does is encapsulated, and the recursion separate, but this makes the recursion less obvious.

I think it also helps to use real world problems, such as traversing a directory hierarchy or other tree structure.

Answer 6

So I will be the blunt one here, you will either get recursion or you wont and there is absolutely nothing wrong with that. It is just one of those things that separates programmers (sad but true according to Joel). Now to explain recursion like you are five is where the task becomes a little murky. Imagine you have four (4) apples and every time I ask you to count them you take one of your apples and give it to me. The first time I talk to you you will tell me you have four apples and hand one to me. Now we continue this process until you have zero apples this will be analogous to what others have called the base case or exit statement which ensures that your function will terminate.

Now, you are no longer five, if I asked you to prove that for all instances of N that this would work how would you do that? This is what your professor is getting at when he states to solve a problem via induction. An example of how to solve by induction would be the following: I have six cans of Mountain Dew on my desk and I am in the process of drinking one of them. I say "Wow this can of Mountain Dew tastes like an electric rainbow." I would use induction to say that the other five cans and by extension all cans of Mountain Dew taste like electric rainbows. So in the case of recursion, you prove that a function will both terminate and be correct utilizing the same process.

It may help to solve a "trivial" instance of the problem such as blah(0) and blah(1) and blah(2) this will show you that the solution trends in the direction that you anticipate as well as the fact you can use induction to say this process will terminate given any input N.