It would maybe be best to look at it from more of a mathematical perspective. After all, recursion is rooted in mathematics, as is most of computer science.

I am not saying you need to start cranking out math problems, but once you understand the mathematical concepts, programming them becomes much simpler. A good book on data structures and algorithms is a must.

For example, the Fibonacci sequence.

Code:

#include <stdio.h>
#include <stdlib.h>
/* returns the n'th fibonacci number */
int fibonacci(int n);
int main(int argc, char **argv)
{
int num;
if (argc == 2) {
num = atoi(argv[1]);
printf("fibonacci(%d) = %d\n",num,fibonacci(num));
}
return 0;
}
int fibonacci(int n)
{
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else if (n > 1) {
return fibonacci(n - 1) + fibonacci(n - 2);
} else {
printf("Must be postive integer\n");
return -1;
}
}

The Fibonacci sequence is a recursively defined as F(n) = F(n-1) + F(n-2) and the bascases are 0, if n == 0, and 1 if n == 1.

The Fibonacci sequence is a very famous problem, and usually used to introduce recursion to computer science students.