Recursion is all about trust.

Image credit: http://www.cr31.co.uk/logoarts/

The secret of recursion is only one thing. Trust. Here's a neat example to show you what it exactly means. Quoting Stephan van Hulst from Code Ranch here.

Say there's a long queue of people, and you want to know how many are in the queue. You can simply ask the guy in front of you how many people there are in the queue, and then add 1 for yourself. You don't care how the guy in front of you got the answer, you just trust that it's correct. The guy in front uses the same technique. This goes on all the way until the guy at the front of the queue is asked how many people there are in the queue. The guy at the front sees no people in front of him, so he just reports 1. He is the base case.

final class PersonInQueue {
 
  private final PersonInQueue next;
 
  int askForLengthOfQueue() {
    if (next == null)
      return 1;
 
    return next.askForLengthOfQueue() +1;
  }
}

Here's the post: Algorithm explanation if you want to have a look. The question was on Tower of Hanoi.