You have now seen four recursive problems: factorial, sum of digits, GCD, and power. Here is what they teach:
Every recursive function needs a base case that stops the recursion.
The recursive case must move toward the base case.
Trust the recursion. Assume smaller problems will be solved correctly.
Sometimes you can reduce the problem by more than (GCD halves the range, power halves the exponent). These patterns apply to all recursive problems. But recursion has limits. Some recursive solutions repeat the same work millions of times. What fixes that? The next section shows you.