Recursion always works the same. Keep going until you find a satisfied result, otherwise, try again. With the first example, the check is on the length of the provided string, once it hits 0 there is no more recursion. Examples are hard to do though, so you need to follow a stack trace. With just the word 'The', you would end up with:
firstChar1 = 'T'
firstChar2 = 'e';
So the end result would be 'eT'. The answer appears wrong since the recursion only works from the third character on. That should be fetching from substring(1).
You never need to work with an increment when dealing with recursion. This is because the parameter should be modified to match only the remaining options. So with a vowel counter you would need
SUB COUNTVOWELS(STRING input)
SET iTotal TO 0
IF input.LENGTH > 0 THEN
SET sEvaluate TO input.SUBSTRING(0, 1)
IF sEvaluate.ISVOWEL() THEN
SET iTotal TO 1
SET iTotal TO iTotal + (CALL COUNTVOWELS(input.SUBSTRING(1)))
ISVOWEL can actually be done from either the Character class, or by comparing. This is wrong though:
if ( vowel == "a" || vowel == "A"
. Strings cannot be compared this way. If you stick to string, you need to use vowel.equals("a") or vowel.equalsIgnoreCase("a").
Sorry, the above is pseudo code. Please implement it and come back if it gives you any trouble.