Write your answer without recursion to begin with.
There really isn't anything mysterious, it is just a function call disguised as a loop.
Eg, two strlen functions.
Code:
int mylen ( const char *s ) {
int i;
for ( i = 0 ; *s++ ; i++ );
return i;
}
int mylen ( const char *s ) {
if ( *s == '\0' ) return 0;
else return 1 + mylen(s+1);
}
In the case of strlen, the base case is when the length is zero, and the answer is therefore "obvious".
Otherwise, the recursive step is to solve part of the problem (string is at least 1 char long), then call recursively to work out the length of the tail of the string.