Functions and Recursively Defined Functions

---

Functions and Recursively Defined Functions

---

1. Functions

A function is a relation between two sets that associates each element of one set (the domain) to exactly one element of another set (the codomain). A function is often denoted as:

$$f: A \to B$$

where $A$ is the domain and $B$ is the codomain. For each element $a \in A$, there exists exactly one element $b \in B$ such that $f(a) = b$. The element $b$ is called the image of $a$ under the function $f$.

Components of a Function:

1. Domain (A): The set of inputs or arguments.
2. Codomain (B): The set of possible outputs.
3. Rule (f): The rule that assigns each element from the domain to an element in the codomain.

Example of a Function:

Let $f: \mathbb{R} \to \mathbb{R}$ be the function defined by:

$$f(x) = x^2$$

This function maps each real number $x$ to its square $x^2$.

---

2. Types of Functions

a) One-to-One (Injective) Function

A function $f: A \to B$ is one-to-one (or injective) if different elements in $A$ map to different elements in $B$. That is, if $f(a_1) = f(a_2)$, then $a_1 = a_2$.

Example:
The function $f(x) = 2x$, where $f: \mathbb{R} \to \mathbb{R}$, is injective because if $f(x_1) = f(x_2)$, then $2x_1 = 2x_2$, which implies $x_1 = x_2$.

---

b) Onto (Surjective) Function

A function $f: A \to B$ is onto (or surjective) if every element in $B$ is the image of at least one element in $A$. In other words, for every $b \in B$, there is an $a \in A$ such that $f(a) = b$.

Example:
The function $f(x) = \sin(x)$, where $f: \mathbb{R} \to [-1, 1]$, is surjective because for every value $y \in [-1, 1]$, there exists an $x \in \mathbb{R}$ such that $f(x) = y$.

---

c) One-to-One Correspondence (Bijective) Function

A function $f: A \to B$ is bijective if it is both injective and surjective. This means every element of $A$ maps to a unique element in $B$, and every element of $B$ is the image of exactly one element from $A$.

Example:
The function $f(x) = x + 1$, where $f: \mathbb{R} \to \mathbb{R}$, is bijective because it is both injective (no two different values map to the same output) and surjective (every real number is the image of some real number).

---

3. Composition of Functions

The composition of two functions $f: A \to B$ and $g: B \to C$ is a new function $g \circ f: A \to C$ defined by:

$$(g \circ f)(x) = g(f(x))$$

In other words, the output of $f(x)$ is used as the input for $g$.

Example:
Let $f(x) = x + 1$ and $g(x) = 2x$, where $f: \mathbb{R} \to \mathbb{R}$ and $g: \mathbb{R} \to \mathbb{R}$. The composition $g \circ f$ is:

$$(g \circ f)(x) = g(f(x)) = g(x + 1) = 2(x + 1) = 2x + 2$$

---

4. Recursively Defined Functions

A recursively defined function is a function that is defined in terms of itself. These functions typically have a base case that provides a specific value, and a recursive case that defines the function for other values in terms of the function applied to smaller or simpler inputs.

Structure of a Recursive Function:

1. Base Case: The simplest case(s) that do not use recursion.
2. Recursive Case: The rule that defines the function for larger or more complex inputs, usually in terms of smaller inputs.

---

5. Example of a Recursively Defined Function

a) Factorial Function

The factorial function, denoted $n!$, is defined recursively as follows:

• Base Case: $0! = 1$
• Recursive Case: $n! = n \times (n-1)!$ for $n > 0$

So, we compute $5!$ as:

$$5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$$

This function is defined by using the fact that $n!$ depends on the value of $(n-1)!$.

---

b) Fibonacci Sequence

The Fibonacci sequence is another example of a recursively defined function, where each number is the sum of the two preceding ones:

• Base Cases: $F(0) = 0$, $F(1) = 1$
• Recursive Case: $F(n) = F(n-1) + F(n-2)$ for $n \geq 2$

For example, the first few terms are:

$$F(0) = 0, F(1) = 1, F(2) = F(1) + F(0) = 1 + 0 = 1, F(3) = F(2) + F(1) = 1 + 1 = 2, F(4) = F(3) + F(2) = 2 + 1 = 3, \dots$$

This recursive definition allows for the computation of any Fibonacci number by repeatedly applying the recurrence relation.

---

6. Advantages and Disadvantages of Recursion

Advantages:

• Simplicity: Recursion can simplify the definition of functions that have a natural recursive structure (like factorial, Fibonacci).
• Elegance: Many problems, especially those in mathematics, computer science, and algorithms, are elegantly solved using recursive functions.

Disadvantages:

• Efficiency: Recursive solutions can be less efficient than iterative solutions, especially for problems like Fibonacci, where overlapping subproblems lead to redundant calculations.
• Stack Overflow: Deep recursion can lead to a stack overflow error, where the computer runs out of memory for storing function calls.

---

7. Tail Recursion

A recursive function is said to be tail-recursive if the recursive call is the last operation in the function. Tail recursion is more efficient because it allows the compiler to optimize the recursion (by reusing the same stack frame).

Example: A tail-recursive version of the factorial function:

$$\text{factorial}(n, acc) = \begin{cases} acc & \text{if } n = 0 \\ \text{factorial}(n-1, n \times acc) & \text{if } n > 0 \end{cases}$$

Where $acc$ is an accumulator that stores the result of the factorial computation as we go along.

---