Recursive Functions

ACSL recursive function problems give you a mathematical definition and ask you to evaluate it for a specific input. The key skill isn’t understanding recursion conceptually - it’s tracing calls quickly and accurately without losing your place.

How ACSL recursive problems work

Every recursive function has two parts:

1. Base case(s) - a condition where the function returns a value directly
2. Recursive case(s) - the function calls itself with different arguments

Example:

$f(x)=\{\begin{array}{ll}2\cdot f(x-1)+1& \text{if }x>0\\ 3& \text{if }x\le 0\end{array}$

To find $f(3)$, you trace downward until you hit a base case, then work back up.

The trace-down, compute-up method

This is the most reliable technique. Write each call on its own line going down, then fill in values going up.

Find $f(3)$ using the function above:

Trace down:

$\begin{array}{rl}f(3)& =2\cdot f(2)+1\\ f(2)& =2\cdot f(1)+1\\ f(1)& =2\cdot f(0)+1\\ f(0)& =3\text{(base case)}\end{array}$

Compute up:

$\begin{array}{rl}f(0)& =3\\ f(1)& =2\cdot 3+1=7\\ f(2)& =2\cdot 7+1=15\\ f(3)& =2\cdot 15+1=31\end{array}$

Answer: 31

Speed tip: Write the trace as a neat column. Sloppy work is the #1 source of errors on recursive function problems.

Try it: trace a recursive function

Step through the evaluation of $f(3)$ where $f(x)=2\cdot f(x-1)+1$ if $x>0$, else $3$.

1f(x) = 2·f(x-1) + 1    (if x > 0)2f(x) = 3                (if x is 0 or less)34Trace down (expand until base case):5  f(3) = 2·f(2) + 16  f(2) = 2·f(1) + 17  f(1) = 2·f(0) + 18  f(0) = 3              [base case]910Compute up (substitute values back):11  f(0) = 312  f(1) = 2·3 + 1 = 713  f(2) = 2·7 + 1 = 1514  f(3) = 2·15 + 1 = 31

Trace down: expand each call

Multi-branch recursion (Fibonacci-style)

Some functions call themselves more than once. These are trickier because the call tree branches.

Example:

$g(x)=\{\begin{array}{ll}g(x-1)+g(x-2)& \text{if }x>1\\ 1& \text{if }x=1\\ 0& \text{if }x=0\end{array}$

For $g(6)$, build a table from the bottom up instead of tracing down:

$\begin{array}{rl}g(0)& =0\\ g(1)& =1\\ g(2)& =g(1)+g(0)=1+0=1\\ g(3)& =g(2)+g(1)=1+1=2\\ g(4)& =g(3)+g(2)=2+1=3\\ g(5)& =g(4)+g(3)=3+2=5\\ g(6)& =g(5)+g(4)=5+3=8\end{array}$

Answer: 8

Key insight: For multi-branch recursion, always build bottom-up. Tracing top-down creates a tree that’s easy to mess up. Bottom-up is a simple table.

Multi-condition functions

ACSL loves functions with 3+ conditions. Read them carefully - the conditions determine which rule to apply at each step.

Example:

$h(x)=\{\begin{array}{ll}h(x-2)+3& \text{if }x>10\\ h(x-1)\cdot 2& \text{if }5<x\le 10\\ x& \text{if }x\le 5\end{array}$

Find $h(14)$:

$\begin{array}{rl}h(14)& :x>10,\text{ so }=h(12)+3\\ h(12)& :x>10,\text{ so }=h(10)+3\\ h(10)& :5<x\le 10,\text{ so }=h(9)\cdot 2\\ h(9)& :5<x\le 10,\text{ so }=h(8)\cdot 2\\ h(8)& :5<x\le 10,\text{ so }=h(7)\cdot 2\\ h(7)& :5<x\le 10,\text{ so }=h(6)\cdot 2\\ h(6)& :5<x\le 10,\text{ so }=h(5)\cdot 2\\ h(5)& :x\le 5,\text{ base case}=5\end{array}$

Now compute up:

$\begin{array}{rl}h(5)& =5\\ h(6)& =5\cdot 2=10\\ h(7)& =10\cdot 2=20\\ h(8)& =20\cdot 2=40\\ h(9)& =40\cdot 2=80\\ h(10)& =80\cdot 2=160\\ h(12)& =160+3=163\\ h(14)& =163+3=166\end{array}$

Answer: 166

Watch out: Notice how the rule changed at $h(10)$. The most common mistake is applying the wrong rule when crossing a boundary.

Two-parameter functions

These appear at higher difficulty levels. Track both parameters carefully.

Example:

$f(x,y)=\{\begin{array}{ll}f(x-y,y-1)+2& \text{if }x>y\\ x+y& \text{if }x\le y\end{array}$

Find $f(12,6)$:

$\begin{array}{rl}f(12,6)& :12>6,\text{ so }=f(6,5)+2\\ f(6,5)& :6>5,\text{ so }=f(1,4)+2\\ f(1,4)& :1\le 4,\text{ base case}=1+4=5\end{array}$

Compute up:

$\begin{array}{rl}f(1,4)& =5\\ f(6,5)& =5+2=7\\ f(12,6)& =7+2=9\end{array}$

Answer: 9

Indirect recursion

Occasionally ACSL gives two functions that call each other.

Example:

$f(x)=\{\begin{array}{ll}g(x-1)+1& \text{if }x>0\\ 0& \text{if }x\le 0\end{array}g(x)=\{\begin{array}{ll}f(x-2)\cdot 2& \text{if }x>0\\ 1& \text{if }x\le 0\end{array}$

Find $f(5)$:

$\begin{array}{rl}f(5)& =g(4)+1\\ g(4)& =f(2)\cdot 2\\ f(2)& =g(1)+1\\ g(1)& =f(-1)\cdot 2\\ f(-1)& =0\text{(base case)}\end{array}$

Compute up:

$\begin{array}{rl}f(-1)& =0\\ g(1)& =0\cdot 2=0\\ f(2)& =0+1=1\\ g(4)& =1\cdot 2=2\\ f(5)& =2+1=3\end{array}$

Answer: 3

Common mistakes

1. Applying the wrong condition. Always re-check which branch applies for the current value of x before computing.
2. Arithmetic errors during compute-up. Double-check each line - one wrong value cascades through everything above it.
3. Miscounting with multi-branch. Use the bottom-up table method for Fibonacci-style problems. Don’t try to trace the tree in your head.
4. Forgetting that base cases can be different. $g(0)=0$ and $g(1)=1$ are two separate base cases.

Contest strategy

• Simple single-recursion: ~30 seconds
• Multi-condition: ~60 seconds (be methodful)
• Multi-branch (Fibonacci): ~45 seconds with bottom-up table
• Two-parameter: ~60 seconds (track both values carefully)
• When in doubt, write it out. Mental math causes mistakes here.