Let's look at the canonical example, factorial.

Factorial, denoted with the ! operator, is defined as:

n! = n * (n-1) * ... * 1

For example, 5! = 5 * 4 * 3 * 2 * 1 = 120

The recursive implementation for factorial is as follows:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

We know from its definition that 0! is 1. Since n == 0 is the smallest number we can compute the factorial of, we use it as our base case. The recursive step also follows from the definition of factorial, i.e., n! = n * (n-1)!.

Recursive functions have three important components:

1. Base case. You can think of the base case as the case of the simplest function input, or as the stopping condition for the recursion.

   In our example, factorial(0) is our base case for the factorial function.

2. Recursive call on a smaller problem. You can think of this step as calling the function on a smaller problem that our current problem depends on. We assume that a recursive call on this smaller problem will give us the expected result; we call this idea the "recursive leap of faith".

   In our example, factorial(n) depends on the smaller problem of factorial(n-1).

3. Solve the larger problem. In step 2, we found the result of a smaller problem. We want to now use that result to figure out what the result of our current problem should be, which is what we want to return from our current function call.

   In our example, we can compute factorial(n) by multiplying the result of our smaller problem factorial(n-1) (which represents (n-1)!) by n (the reasoning being that n! = n * (n-1)!).

The next few questions in lab will have you writing recursive functions. Here are some general tips:

• Paradoxically, to write a recursive function, you must assume that the function is fully functional before you finish writing it; this is called the recursive leap of faith.
• Consider how you can solve the current problem using the solution to a simpler version of the problem. The amount of work done in a recursive function can be deceptively little: remember to take the leap of faith and trust the recursion to solve the slightly smaller problem without worrying about how.
• Think about what the answer would be in the simplest possible case(s). These will be your base cases - the stopping points for your recursive calls. Make sure to consider the possibility that you're missing base cases (this is a common way recursive solutions fail).
• It may help to write an iterative version first.

For example, this is the Virahanka-Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, ....

Each term is the sum of the previous two terms. This tree-recursive function calculates the nth Virahanka-Fibonacci number.

def virfib(n):
    if n == 0 or n == 1:
        return n
    return virfib(n - 1) + virfib(n - 2)

Calling virfib(6) results in a call structure that resembles an upside-down tree (where f is virfib):

Each recursive call f(i) makes a call to f(i-1) and a call to f(i-2). Whenever we reach an f(0) or f(1) call, we can directly return 0 or 1 without making more recursive calls. These calls are our base cases.

A base case returns an answer without depending on the results of other calls. Once we reach a base case, we can go back and answer the recursive calls that led to the base case.

As we will see, tree recursion is often effective for problems with branching choices. In these problems, you make a recursive call for each branching choice.