Recursion is a programming technique in which a function calls itself to solve a problem. Tracing recursion involves understanding how the function calls are made and the order in which they are executed. Here's an example to demonstrate how recursion works and how to trace its execution:

Let's consider a simple recursive function to calculate the factorial of a number:

int factorial(int n) {

    // Base case: factorial of 0 is 1

    if (n == 0) {

        return 1;

    }

    // Recursive case: factorial of n is n multiplied by factorial of (n-1)

    return n * factorial(n - 1);

}

```

Now, let's trace the execution of `factorial(5)` to understand how recursion works:

1. `factorial(5)` is called.

2. Since 5 is not equal to 0, the function enters the recursive case.

3. The function returns `5 * factorial(4)`.

4. `factorial(4)` is called.

5. Again, 4 is not equal to 0, so the function returns `4 * factorial(3)`.

6. `factorial(3)` is called.

7. Following the same pattern, the function returns `3 * factorial(2)`.

8. `factorial(2)` is called.

9. The function returns `2 * factorial(1)`.

10. `factorial(1)` is called.

11. The function returns `1 * factorial(0)`.

12. `factorial(0)` is called.

13. Since 0 is the base case, the function returns 1.

14. The previous call `factorial(1)` evaluates to `1 * 1`, returning 1.

15. Similarly, `factorial(2)` evaluates to `2 * 1`, returning 2.

16. `factorial(3)` evaluates to `3 * 2`, returning 6.

17. `factorial(4)` evaluates to `4 * 6`, returning 24.

18. Finally, `factorial(5)` evaluates to `5 * 24`, returning 120.

By tracing the recursive calls, you can see how the function breaks down the problem into smaller subproblems until it reaches the base case, and then combines the results to obtain the final solution.

It's important to note that proper base cases are essential to ensure that the recursion terminates. Without a base case, the function would continue to call itself indefinitely, resulting in a stack overflow or infinite recursion.

Tracing recursion helps in understanding the flow of execution and how the function builds up the solution by combining results from smaller instances of the same problem.