Induction and Recursion (Part B)
CSI 2101: Discrete Structures
School of Electrical Engineering and Computer Science, University of Ottawa
March 09, 2021
Copyright By PowCoder代写 加微信 powcoder
Md. Hasan (uOttawa) Discrete Structures 5b MdH W22 March 09, 2021 1 / 18
1 Recursive Definitions
2 Structural Induction
3 Recursive Algorithms
Md. Hasan (uOttawa) Discrete Structures 5b MdH W22 March 09, 2021 2 / 18
Recursion: the process of defining an object in terms of itself.
It is used to define sequences, functions, and sets.
• Mathematical induction and strong induction are used to prove results
relevant to recursive sequences and functions.
• Structural induction is used to prove results relevant to recursive sets.
Md. Hasan (uOttawa) Discrete Structures 5b MdH W22 March 09, 2021 3 / 18
Recursive Functions
Recursively Defined Functions
We use two steps to define a function with the set of nonnegative integers
as its domain:
Basis Step: Specify the value of the function at zero.
Recursive Step: Give a rule for finding its value at an integer from its value at smaller integers.
Give a recursive definition of an, where a is a nonzero real number and n is
a nonnegative integer.
– (Basis Step) a0 = 1 (the value at zero)
– (Resursive Step) an+1 = a · an, for n = 0, 1, 2, … (the rule for finding)
Md. Hasan (uOttawa) Discrete Structures 5b MdH W22 March 09, 2021 4 / 18
Recursive Functions (cont.)
Fibonacci Numbers
f0 =0,f1 =1,and
fn = fn−1 + fn−2, for n ≥ 2.
Show that whenever n ≥ 3, fn > αn−2, where α = (1 + √5)/2.
Md. Hasan (uOttawa) Discrete Structures 5b MdH W22 March 09, 2021 5 / 18
Recursive Sets and Structures
The set Σ∗ of strings over the alphabet Σ is defined recursively by
• Basis Step: λ ∈ Σ∗ (where λ is the empty string containing no symbols). • Recursive Step: If w ∈ Σ∗ and x ∈ Σ, then w||x ∈ Σ∗.
Two strings can be combined via the operation of concatenation. Let Σ be the set of symbols and Σ∗ the set of strings formed from symbols in Σ. We can define the concatenation of two strings recursively as follows
• Basis Step: If w ∈ Σ∗, then w||λ = w, where λ is the empty string. • Recursive Step: If w1 ∈ Σ∗ and w2 ∈ Σ∗ and x ∈ Σ, then
w1||(w2||x) = (w1||w2)||x.
Md. Hasan (uOttawa) Discrete Structures 5b MdH W22 March 09, 2021 6 / 18
Recursive Sets and Structures (cont.)
Give a recursive definition of l(w), the length of the string w.
Use structural induction to prove that l(xy) = l(x) + l(y), where x and y belong to Σ∗, the set of strings over the alphabet Σ.
Md. Hasan (uOttawa) Discrete Structures 5b MdH W22 March 09, 2021 7 / 18
Reversal of a String
Reversal of a string is given by the following steps
Basis Step: λR = λ
Recursive Step: If w ∈ Σ∗ and x ∈ Σ, then (wx )R = x · w R .
Md. Hasan (uOttawa) Discrete Structures 5b MdH W22 March 09, 2021 8 / 18
Structural Induction
Structural Induction is used to prove a property of the elements of a recursively defined set. A proof by structural induction consists of the following parts.
• Basis Step: Show that the result holds for all elements specified in the basis step of the recursive definition.
• Recursive Step: Show that if the statement is true for each of the elements used to construct new elements in the recursive step of the definition, the result holds for these new elements.
Md. Hasan (uOttawa) Discrete Structures 5b MdH W22 March 09, 2021 9 / 18
Tree Structures
Rooted Trees
The set of rooted trees where a rooted tree where a rooted tree consists of a set of vertices containing a distinguished vertex called the root, and edges connecting these vertices, can be defined recursively by these steps:
Basis Step:
A single vertex r is a rooted tree.
Recursive Step:
Suppose that T1, T2, …, Tn are disjoint rooted trees with roots r1, r2, …, rn, respectively. Then the graph formed by starting with a root r, which is not in any of the rooted trees T1, T2, …, Tn, and adding an edge from r to each of the vertices r1, r2, …, rn, is also a rooted tree.
Md. Hasan (uOttawa) Discrete Structures 5b MdH W22 March 09, 2021 10 / 18
Tree Structures (cont.)
Extended Binary Trees
The set of extended binary trees can be defined recursively by these
Basis Step:
The empty set is an extended binary tree.
Recursive Step:
If T1 and T2 are disjoint extended binary trees, there is an extended binary tree, denoted by T1 · T2, consisting of a root r together with edges connecting the root to each of the roots of the left subtree T1 and the right subtree T2 when these trees are nonempty.
Md. Hasan (uOttawa) Discrete Structures 5b MdH W22 March 09, 2021 11 / 18
Tree Structures (cont.)
Full Binary Trees
The set of full binary trees can be defined recursively by these steps:
Basis Step:
There is a full binary tree consisting only of a single vertex r. Recursive Step:
If T1 and T2 are disjoint full binary trees, there is a full binary tree, denoted by T1 · T2, consisting of a root r together with edges connecting the root to each of the roots of the left subtree T1 and the right subtree T2.
Md. Hasan (uOttawa) Discrete Structures 5b MdH W22 March 09, 2021 12 / 18
Height and Size of a Full Binary Tree
The height of a full binary tree T is denoted by h(T). It is defined as Basis Step: The height of the full binary tree T consisting of only a root r
is h(T) = 0.
Recursive Step: If T1 and T2 are full binary trees, then the full binary tree
T = T1 ·T2, has height h(T) = 1+max(h(T1),h(T2)).
The size of a full binary tree T is denoted by n(T). It is dfeined as the
number of vertices in a full binary tree.
Basis Step: The number of vertices n(T) of the full binary tree T consisting of only a root r is n(T ) = 1.
Recursive Step: If T1 and T2 are full binary trees, then the number of vertices of the full binary tree T = T1 · T2 is n(T) = 1 + n(T1) + n(T2).
Md. Hasan (uOttawa) Discrete Structures 5b MdH W22 March 09, 2021 13 / 18
Height and Size of a Full Binary Tree (cont.)
Theorem If T is a full binary tree, then n(T) ≤ 2h(T)+1 − 1.
Basis Step: For the full binary tree consisting of just the root r, the result
is true because n(T) = 1 and h(T) = 0.
Recursive Step: For the inductive hypothesis, we assume that
n(T1) ≤ 2h(T1)+1 − 1 and n(T2) ≤ 2h(T2)+1 − 1 whenever T1 and T2 are full binary trees.
This implies n(T ) = 1 + n(T1) + n(T2) and
h(T) = 1 + max(h(T1),h(T2)).
…… (using the inductive hypothesis and recurisve definition) n(T) ≤ 2h(T)+1 − 1
Md. Hasan (uOttawa) Discrete Structures 5b MdH W22 March 09, 2021 14 / 18
Algorithms
An algorithm is called recursive if it solves a problem by reducing it to an instance of the same problem with smaller input.
A recursive algorithm for computing n!.
procedure factorial (n: nonnegative integer) if n = 0 then return 1
if else return n·factorial(n − 1)
{Output is n!}
Md. Hasan (uOttawa) Discrete Structures 5b MdH W22 March 09, 2021 15 / 18
Algorithm Correctness
Prove that the following algorithm is correct.
A recursive algorithm for computing an.
procedure power(a: nonzero real number, n: nonnegative integer) if n = 0 then return 1
else return a·power(a,n−1)
{output is an}
Md. Hasan (uOttawa) Discrete Structures 5b MdH W22 March 09, 2021 16 / 18
Algorithm Correctness (cont.)
Mathematical induction can be used to prove the given algorithm. Basis Step: If n = 0, the first step tells power (a, 0)=1. This is correct
since a0 = 1 for every nonzero real number a.
Inductive Step: The inductive hypothesis is the statement that power(a,k) = ak for all a ̸= 0 for an arbitrary nonnegative integer k. Thus, the inductive hypothesis is that the algorithm computes ak correctly. If this is true then the algorithm computes ak+1 correctly.
As k + 1 is a positive integer, the algorithm returns
power(a,k +1) = a·power(a,k) = a·ak = ak+1. The algorithm is correct.
Md. Hasan (uOttawa) Discrete Structures 5b MdH W22 March 09, 2021 17 / 18
Thank You!
Questions and Comments?
Md. Hasan (uOttawa) Discrete Structures 5b MdH W22 March 09, 2021 18 / 18
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com