Recursively Defined Functions

Definition

A function $f$ is said to be recursively defined if its value for some inputs is given directly as base value(s), and for all other allowed inputs, the value is defined in terms of values of the same function at smaller inputs.

A recursive definition generally has two parts:

1. Base case(s)

• These give the value of the function for one or more starting inputs.

2. Recursive step

• This gives a rule to compute $f(n)$ from earlier values such as $f(n-1)$, $f(n-2)$, etc.

General form

For a function on natural numbers, a recursive definition often looks like:

• $f(0) = a$
• $f(n) = \text{an expression involving } f(n-1), f(n-2), \dots \text{ for } n \ge 1$

Example

Factorial can be defined recursively as:

• $0! = 1$
• $n! = n \cdot (n-1)!$, for $n \ge 1$

This means every factorial value is built from the previous one.

---

Main Content

1. Base Cases and Recursive Rules

Base case(s)

• are the foundation of a recursive definition. Without them, the recursion would continue forever and never produce an actual value. They anchor the function at known input(s) and make the definition complete.
• Example: For factorial, $0! = 1$ is the base case.
• Example: For Fibonacci numbers, $F_0 = 0$ and $F_1 = 1$ are base cases.

Recursive rule

• explains how to generate the next value from earlier value(s). This is the heart of the definition because it provides the mechanism for building the function step by step.
• Example: $n! = n \cdot (n-1)!$
• Example: $F_n = F_{n-1} + F_{n-2}$ for $n \ge 2$

A well-defined recursive function must have:

• enough base cases to start the computation,
• a rule that eventually reduces every input to a base case,
• no ambiguity in how values are generated.

Example: Factorial

$$\begin{aligned} 0! &= 1 \\ 1! &= 1 \cdot 0! = 1 \\ 2! &= 2 \cdot 1! = 2 \\ 3! &= 3 \cdot 2! = 6 \\ 4! &= 4 \cdot 3! = 24 \end{aligned}$$

This shows how each value depends on the previous one.

Example: Fibonacci sequence

$$F_0 = 0,\quad F_1 = 1,\quad F_n = F_{n-1} + F_{n-2}\ (n \ge 2)$$

Then:

• $F_2 = 1$
• $F_3 = 2$
• $F_4 = 3$
• $F_5 = 5$

This sequence is recursive because each term is defined from earlier terms.

---

2. Recursive Computation and Evaluation

• A recursively defined function is evaluated by repeatedly applying the recursive rule until reaching the base case. This process is sometimes called unfolding the recursion.
• Recursive evaluation is useful when the function follows a natural pattern, but it may be inefficient if values are recomputed many times, especially for sequences like Fibonacci.

Example: Evaluating $4!$

Using the recursive definition: $$4! = 4 \cdot 3!$$ $$3! = 3 \cdot 2!$$ $$2! = 2 \cdot 1!$$ $$1! = 1 \cdot 0!$$ $$0! = 1$$

Substitute back: $$4! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 24$$

Example: Evaluating $F_5$

$$F_5 = F_4 + F_3$$ $$F_4 = F_3 + F_2,\quad F_3 = F_2 + F_1$$ $$F_2 = F_1 + F_0 = 1 + 0 = 1$$

Then: $$F_3 = 1 + 1 = 2,\quad F_4 = 2 + 1 = 3,\quad F_5 = 3 + 2 = 5$$

Key idea

Recursive computation is a systematic chain:

• start from the given input,
• break it into smaller subproblems,
• continue until a base case is reached,
• combine the results back.

This is the same logic used in recursive algorithms in programming and in inductive mathematical proofs.

---

3. Recursion, Induction, and Well-Definedness

Mathematical induction

• is the proof technique most closely related to recursive definitions. If a function is defined recursively, then induction is often used to prove its properties.
• Base step: verify the property for the base case.
• Inductive step: assume it holds for smaller values and prove it for the next value.

Well-definedness

• means the recursive rule must assign exactly one value to each allowed input. A recursive definition is valid only if every value can eventually be traced back to a base case in a unique way.

Example of induction with factorial

Prove: $$n! \ge 1 \quad \text{for all } n \ge 0$$

• Base case: $0! = 1 \ge 1$
• Inductive step: assume $k! \ge 1$. Then $$(k+1)! = (k+1)\cdot k! \ge 1 \cdot 1 = 1$$ So the property holds for all natural numbers.

Example of a recursively defined sum

Define: $$S(n) = 1 + 2 + \cdots + n$$ Recursively:

• $S(1)=1$
• $S(n)=S(n-1)+n$, for $n\ge2$

This is well-defined because every $S(n)$ reduces to $S(1)$.

Why this matters

A recursive definition must not:

• loop endlessly without reaching a base case,
• depend on future values,
• give conflicting values for the same input.

For example, if one tried to define $$f(n)=f(n+1)+1$$ with no base case, the function would not be practically evaluable for natural numbers. It lacks a terminating foundation.

---

Working / Process

1. Identify the starting value(s)

• Determine which input values must be given directly.
• These are the base cases that begin the function.
• Example: $F_0 = 0$, $F_1 = 1$

2. Write the recursive rule

• Express the function for larger inputs in terms of smaller inputs.
• Make sure each recursive step moves closer to the base case.
• Example: $F_n = F_{n-1} + F_{n-2}$

3. Evaluate or verify using repeated substitution or induction

• To compute a value, repeatedly replace the function by smaller values until a base case is reached.
• To prove a property, use mathematical induction based on the recursive structure.
• Example: to evaluate $F_5$, compute $F_4$, $F_3$, $F_2$, and so on until the base values are used.

---

Advantages / Applications

Natural representation of patterns

• Recursive functions describe many mathematical patterns in a compact and intuitive way.
• They are ideal for sequences, counting problems, and structures built step by step.
• Example: factorial, Fibonacci numbers, powers of 2, and summations.

Foundation for induction and theorem proving

• Recursive definitions and induction work together very closely.
• Many properties of recursively defined functions are proved using induction.
• This is essential in discrete mathematics and formal reasoning.

Important in algorithms and computation

• Recursion is a core idea in computer science, especially in recursive algorithms, divide-and-conquer methods, parsing, tree traversal, and dynamic programming.
• Examples include merge sort, binary search, and recursive tree functions.

---

Summary

Recursively defined functions build values from earlier values together with one or more base cases. They are widely used to define sequences and mathematical processes in a compact and structured way. Their recursive nature makes them closely connected to induction, proof techniques, and algorithm design.