I'm not sure that having "faith" is the correct way of going about learning recursion.
It's probably better to start off with a few small examples and use substitution to figure out what's going on, usually operations on lists are done because they're generally of the correct form. This in turn makes functional languages a nice choice for learning recursion because lists are usually the collection primitive in such languages.
A trivial example: find the length of a list.
We'll call our function length. If we give it the list [1,2,3] it should return 3.
A quick definition for length
And the expansion of length [1,2,3]:
length list =
if list ==  --is list equal to an empty list
then 0 --an empty list's length is 0
else 1 + length (tail list) --tail removes the first element of a list
Here's a couple example problems for you to start with:
1 + (length [2,3])
1 + 1 + (length )
1 + 1 + 1 + (length )
1 + 1 + 1 + 0
1 + 1 + 1
1 + 2
- determine if an element is in a list (if you're using a static language, use integers for simplicity)
- reverse a list