Discrete Mathematics
Chapter 4: Induction and Recursions
Department of Mathematics
The FPT university
TrungDT (FUHN) MAD101 Chapter 4 1 / 18
Chapter 4: Introduction
TrungDT (FUHN) MAD101 Chapter 4 2 / 18
Chapter 4: Introduction
Topics covered:
TrungDT (FUHN) MAD101 Chapter 4 2 / 18
Chapter 4: Introduction
Topics covered:
4.1 Mathematical Induction
TrungDT (FUHN) MAD101 Chapter 4 2 / 18
Chapter 4: Introduction
Topics covered:
4.1 Mathematical Induction
4.2 Strong Induction and Well-Ordering
TrungDT (FUHN) MAD101 Chapter 4 2 / 18
Chapter 4: Introduction
Topics covered:
4.1 Mathematical Induction
4.2 Strong Induction and Well-Ordering
4.3 Recursive Definitions and Structural Induction
TrungDT (FUHN) MAD101 Chapter 4 2 / 18
Chapter 4: Introduction
Topics covered:
4.1 Mathematical Induction
4.2 Strong Induction and Well-Ordering
4.3 Recursive Definitions and Structural Induction
4.4 Recursive Algorithms
TrungDT (FUHN) MAD101 Chapter 4 2 / 18
Chapter 4: Introduction
Topics covered:
4.1 Mathematical Induction
4.2 Strong Induction and Well-Ordering
4.3 Recursive Definitions and Structural Induction
4.4 Recursive Algorithms
4.5 Program Correctness
TrungDT (FUHN) MAD101 Chapter 4 2 / 18
4.1 Mathematical Induction
TrungDT (FUHN) MAD101 Chapter 4 3 / 18
4.1 Mathematical Induction
Problem. Prove that the statement P(n) is true for all n = 1, 2, . . .
TrungDT (FUHN) MAD101 Chapter 4 3 / 18
4.1 Mathematical Induction
Problem. Prove that the statement P(n) is true for all n = 1, 2, . . .
Proof by Induction:
TrungDT (FUHN) MAD101 Chapter 4 3 / 18
4.1 Mathematical Induction
Problem. Prove that the statement P(n) is true for all n = 1, 2, . . .
Proof by Induction:
1: Prove that P(1) is true.
TrungDT (FUHN) MAD101 Chapter 4 3 / 18
4.1 Mathematical Induction
Problem. Prove that the statement P(n) is true for all n = 1, 2, . . .
Proof by Induction:
1: Prove that P(1) is true.
2: (Inductive hypothesis) Assume that P(k) is true for some positive
integer k.
TrungDT (FUHN) MAD101 Chapter 4 3 / 18
4.1 Mathematical Induction
Problem. Prove that the statement P(n) is true for all n = 1, 2, . . .
Proof by Induction:
1: Prove that P(1) is true.
2: (Inductive hypothesis) Assume that P(k) is true for some positive
integer k.
3: Prove that P(k + 1) is true.
TrungDT (FUHN) MAD101 Chapter 4 3 / 18
4.1 Mathematical Induction
Problem. Prove that the statement P(n) is true for all n = 1, 2, . . .
Proof by Induction:
1: Prove that P(1) is true.
2: (Inductive hypothesis) Assume that P(k) is true for some positive
integer k.
3: Prove that P(k + 1) is true.
4: Conclusion: P(n) is true for all positive integers n.
TrungDT (FUHN) MAD101 Chapter 4 3 / 18
4.1 Mathematical Induction
Problem. Prove that the statement P(n) is true for all n = 1, 2, . . .
Proof by Induction:
1: Prove that P(1) is true.
2: (Inductive hypothesis) Assume that P(k) is true for some positive
integer k.
3: Prove that P(k + 1) is true.
4: Conclusion: P(n) is true for all positive integers n.
TrungDT (FUHN) MAD101 Chapter 4 3 / 18
TrungDT (FUHN) MAD101 Chapter 4 4 / 18
Example 1. Prove that for all positive integers n we have
n(n + 1)(2n + 1)
12 + 2 2 + 3 2 + · · · + n 2 =
6
TrungDT (FUHN) MAD101 Chapter 4 4 / 18
Example 1. Prove that for all positive integers n we have
n(n + 1)(2n + 1)
12 + 2 2 + 3 2 + · · · + n 2 =
6
Example 2. Prove that n3 − n is divisible by 6 for all integers n ≥ 1.
TrungDT (FUHN) MAD101 Chapter 4 4 / 18
Example 1. Prove that for all positive integers n we have
n(n + 1)(2n + 1)
12 + 2 2 + 3 2 + · · · + n 2 =
6
Example 2. Prove that n3 − n is divisible by 6 for all integers n ≥ 1.
Example 3. Prove that 2n > n2 for all integers n > 4.
TrungDT (FUHN) MAD101 Chapter 4 4 / 18
Example 1. Prove that for all positive integers n we have
n(n + 1)(2n + 1)
12 + 2 2 + 3 2 + · · · + n 2 =
6
Example 2. Prove that n3 − n is divisible by 6 for all integers n ≥ 1.
Example 3. Prove that 2n > n2 for all integers n > 4.
Example 4. Let n be a positive integer. Prove that every checkerboard of
size 2n × 2n with one square removed can be titled by triominoes.
TrungDT (FUHN) MAD101 Chapter 4 4 / 18
4.2 Strong Induction and Well-Ordering
TrungDT (FUHN) MAD101 Chapter 4 5 / 18
4.2 Strong Induction and Well-Ordering
Problem. Prove that P(n) is true for all n = 1, 2, . . .
TrungDT (FUHN) MAD101 Chapter 4 5 / 18
4.2 Strong Induction and Well-Ordering
Problem. Prove that P(n) is true for all n = 1, 2, . . .
Proof by Strong Induction.
TrungDT (FUHN) MAD101 Chapter 4 5 / 18
4.2 Strong Induction and Well-Ordering
Problem. Prove that P(n) is true for all n = 1, 2, . . .
Proof by Strong Induction.
1: Prove that P(1) is true.
TrungDT (FUHN) MAD101 Chapter 4 5 / 18
4.2 Strong Induction and Well-Ordering
Problem. Prove that P(n) is true for all n = 1, 2, . . .
Proof by Strong Induction.
1: Prove that P(1) is true.
2: (Induction hypothesis) Assume that P(1), P(2), . . . , P(k) are all true
for some k ≥ 1.
TrungDT (FUHN) MAD101 Chapter 4 5 / 18
4.2 Strong Induction and Well-Ordering
Problem. Prove that P(n) is true for all n = 1, 2, . . .
Proof by Strong Induction.
1: Prove that P(1) is true.
2: (Induction hypothesis) Assume that P(1), P(2), . . . , P(k) are all true
for some k ≥ 1.
3: Prove that P(k + 1) is also true.
TrungDT (FUHN) MAD101 Chapter 4 5 / 18
4.2 Strong Induction and Well-Ordering
Problem. Prove that P(n) is true for all n = 1, 2, . . .
Proof by Strong Induction.
1: Prove that P(1) is true.
2: (Induction hypothesis) Assume that P(1), P(2), . . . , P(k) are all true
for some k ≥ 1.
3: Prove that P(k + 1) is also true.
4: Conclusion: P(n) is true for all positive integers n.
TrungDT (FUHN) MAD101 Chapter 4 5 / 18
4.2 Strong Induction and Well-Ordering
Problem. Prove that P(n) is true for all n = 1, 2, . . .
Proof by Strong Induction.
1: Prove that P(1) is true.
2: (Induction hypothesis) Assume that P(1), P(2), . . . , P(k) are all true
for some k ≥ 1.
3: Prove that P(k + 1) is also true.
4: Conclusion: P(n) is true for all positive integers n.
Example 1. Prove that every integer greater than 1 can be written as a
product of primes.
TrungDT (FUHN) MAD101 Chapter 4 5 / 18
4.2 Strong Induction and Well-Ordering
Problem. Prove that P(n) is true for all n = 1, 2, . . .
Proof by Strong Induction.
1: Prove that P(1) is true.
2: (Induction hypothesis) Assume that P(1), P(2), . . . , P(k) are all true
for some k ≥ 1.
3: Prove that P(k + 1) is also true.
4: Conclusion: P(n) is true for all positive integers n.
Example 1. Prove that every integer greater than 1 can be written as a
product of primes.
Example 2. Prove that every postage of 12 cents or more can be formed
using only 4-cent and 5-cent stamps.
TrungDT (FUHN) MAD101 Chapter 4 5 / 18
Well-Ordering
TrungDT (FUHN) MAD101 Chapter 4 6 / 18
Well-Ordering
The validity of the Principle of Mathematical Induction follows from the
Well-Ordering property of the set of non-negative integers.
TrungDT (FUHN) MAD101 Chapter 4 6 / 18
Well-Ordering
The validity of the Principle of Mathematical Induction follows from the
Well-Ordering property of the set of non-negative integers.
Well-Ordering
TrungDT (FUHN) MAD101 Chapter 4 6 / 18
Well-Ordering
The validity of the Principle of Mathematical Induction follows from the
Well-Ordering property of the set of non-negative integers.
Well-Ordering
Any nonempty set of non-negative integers has a least element.
TrungDT (FUHN) MAD101 Chapter 4 6 / 18
4.3 Recursive Definitions and Structural Induction
TrungDT (FUHN) MAD101 Chapter 4 7 / 18
4.3 Recursive Definitions and Structural Induction
The Fibonacci {Fn }, n = 1, 2, . . . is defined as follows:
TrungDT (FUHN) MAD101 Chapter 4 7 / 18
4.3 Recursive Definitions and Structural Induction
The Fibonacci {Fn }, n = 1, 2, . . . is defined as follows:
F0 = 0, F1 = 1,
TrungDT (FUHN) MAD101 Chapter 4 7 / 18
4.3 Recursive Definitions and Structural Induction
The Fibonacci {Fn }, n = 1, 2, . . . is defined as follows:
F0 = 0, F1 = 1, and
TrungDT (FUHN) MAD101 Chapter 4 7 / 18
4.3 Recursive Definitions and Structural Induction
The Fibonacci {Fn }, n = 1, 2, . . . is defined as follows:
F0 = 0, F1 = 1, and
Fn = Fn−1 + Fn−2 for n = 2, 3, . . ..
TrungDT (FUHN) MAD101 Chapter 4 7 / 18
4.3 Recursive Definitions and Structural Induction
The Fibonacci {Fn }, n = 1, 2, . . . is defined as follows:
F0 = 0, F1 = 1, and
Fn = Fn−1 + Fn−2 for n = 2, 3, . . ..
This definition is called recursive definition.
TrungDT (FUHN) MAD101 Chapter 4 7 / 18
4.3 Recursive Definitions and Structural Induction
The Fibonacci {Fn }, n = 1, 2, . . . is defined as follows:
F0 = 0, F1 = 1, and
Fn = Fn−1 + Fn−2 for n = 2, 3, . . ..
This definition is called recursive definition.
TrungDT (FUHN) MAD101 Chapter 4 7 / 18
TrungDT (FUHN) MAD101 Chapter 4 8 / 18
Example 1. Find the nth term of the sequence {xn } defined by recursive
definition:
TrungDT (FUHN) MAD101 Chapter 4 8 / 18
Example 1. Find the nth term of the sequence {xn } defined by recursive
definition:
(a) x1 = 5, xn = 3xn−1 for n = 2, 3, . . .
TrungDT (FUHN) MAD101 Chapter 4 8 / 18
Example 1. Find the nth term of the sequence {xn } defined by recursive
definition:
(a) x1 = 5, xn = 3xn−1 for n = 2, 3, . . .
(b) x0 = 2, xn = xn−1 + 1 for n = 1, 2, . . .
TrungDT (FUHN) MAD101 Chapter 4 8 / 18
Example 1. Find the nth term of the sequence {xn } defined by recursive
definition:
(a) x1 = 5, xn = 3xn−1 for n = 2, 3, . . .
(b) x0 = 2, xn = xn−1 + 1 for n = 1, 2, . . .
TrungDT (FUHN) MAD101 Chapter 4 8 / 18
Example 1. Find the nth term of the sequence {xn } defined by recursive
definition:
(a) x1 = 5, xn = 3xn−1 for n = 2, 3, . . .
(b) x0 = 2, xn = xn−1 + 1 for n = 1, 2, . . .
Example 2. Give a recursive definition for the sequence {xn }, n = 1, 2 . . .
whose nth term is:
TrungDT (FUHN) MAD101 Chapter 4 8 / 18
Example 1. Find the nth term of the sequence {xn } defined by recursive
definition:
(a) x1 = 5, xn = 3xn−1 for n = 2, 3, . . .
(b) x0 = 2, xn = xn−1 + 1 for n = 1, 2, . . .
Example 2. Give a recursive definition for the sequence {xn }, n = 1, 2 . . .
whose nth term is:
(a) xn = 7 ∗ 5n+1
TrungDT (FUHN) MAD101 Chapter 4 8 / 18
Example 1. Find the nth term of the sequence {xn } defined by recursive
definition:
(a) x1 = 5, xn = 3xn−1 for n = 2, 3, . . .
(b) x0 = 2, xn = xn−1 + 1 for n = 1, 2, . . .
Example 2. Give a recursive definition for the sequence {xn }, n = 1, 2 . . .
whose nth term is:
(a) xn = 7 ∗ 5n+1
(b) xn = n!
TrungDT (FUHN) MAD101 Chapter 4 8 / 18
Example 1. Find the nth term of the sequence {xn } defined by recursive
definition:
(a) x1 = 5, xn = 3xn−1 for n = 2, 3, . . .
(b) x0 = 2, xn = xn−1 + 1 for n = 1, 2, . . .
Example 2. Give a recursive definition for the sequence {xn }, n = 1, 2 . . .
whose nth term is:
(a) xn = 7 ∗ 5n+1
(b) xn = n!
(c) xn = (−1)n
TrungDT (FUHN) MAD101 Chapter 4 8 / 18
Example 1. Find the nth term of the sequence {xn } defined by recursive
definition:
(a) x1 = 5, xn = 3xn−1 for n = 2, 3, . . .
(b) x0 = 2, xn = xn−1 + 1 for n = 1, 2, . . .
Example 2. Give a recursive definition for the sequence {xn }, n = 1, 2 . . .
whose nth term is:
(a) xn = 7 ∗ 5n+1
(b) xn = n!
(c) xn = (−1)n
(d) xn = 2n − 6
TrungDT (FUHN) MAD101 Chapter 4 8 / 18
Example 1. Find the nth term of the sequence {xn } defined by recursive
definition:
(a) x1 = 5, xn = 3xn−1 for n = 2, 3, . . .
(b) x0 = 2, xn = xn−1 + 1 for n = 1, 2, . . .
Example 2. Give a recursive definition for the sequence {xn }, n = 1, 2 . . .
whose nth term is:
(a) xn = 7 ∗ 5n+1
(b) xn = n!
(c) xn = (−1)n
(d) xn = 2n − 6
TrungDT (FUHN) MAD101 Chapter 4 8 / 18
Recursively Defined Sets and Structures
TrungDT (FUHN) MAD101 Chapter 4 9 / 18
Recursively Defined Sets and Structures
Example 1. Determine the set S defined by:
TrungDT (FUHN) MAD101 Chapter 4 9 / 18
Recursively Defined Sets and Structures
Example 1. Determine the set S defined by:
Basic step: 3 ∈ S
TrungDT (FUHN) MAD101 Chapter 4 9 / 18
Recursively Defined Sets and Structures
Example 1. Determine the set S defined by:
Basic step: 3 ∈ S
Recursive step: If x, y ∈ S then x + y ∈ S
TrungDT (FUHN) MAD101 Chapter 4 9 / 18
Recursively Defined Sets and Structures
Example 1. Determine the set S defined by:
Basic step: 3 ∈ S
Recursive step: If x, y ∈ S then x + y ∈ S
Example 2.
TrungDT (FUHN) MAD101 Chapter 4 9 / 18
Recursively Defined Sets and Structures
Example 1. Determine the set S defined by:
Basic step: 3 ∈ S
Recursive step: If x, y ∈ S then x + y ∈ S
Example 2.
(a) Give a recursive definition for the set of positive integers that are not
divisible by 3
TrungDT (FUHN) MAD101 Chapter 4 9 / 18
Recursively Defined Sets and Structures
Example 1. Determine the set S defined by:
Basic step: 3 ∈ S
Recursive step: If x, y ∈ S then x + y ∈ S
Example 2.
(a) Give a recursive definition for the set of positive integers that are not
divisible by 3
(b) Give a recursive definition for the set of integers that are not divisible
by 3
TrungDT (FUHN) MAD101 Chapter 4 9 / 18
Recursively Defined Sets and Structures
Example 1. Determine the set S defined by:
Basic step: 3 ∈ S
Recursive step: If x, y ∈ S then x + y ∈ S
Example 2.
(a) Give a recursive definition for the set of positive integers that are not
divisible by 3
(b) Give a recursive definition for the set of integers that are not divisible
by 3
TrungDT (FUHN) MAD101 Chapter 4 9 / 18
TrungDT (FUHN) MAD101 Chapter 4 10 / 18
Example 3. Recursive definition for the set of full binary trees.
TrungDT (FUHN) MAD101 Chapter 4 10 / 18
Example 3. Recursive definition for the set of full binary trees.
Basic step: A single vertex is a full binary tree.
TrungDT (FUHN) MAD101 Chapter 4 10 / 18
Example 3. Recursive definition for the set of full binary trees.
Basic step: A single vertex is a full binary tree.
Recursive step: If T1 and T2 are two full binary trees then there is a
full binary tree, denoted by T1 .T2 , consisting of a root r together
with edges connecting this root to the root of the left subtree T1 and
the root of the right subtree T2 .
TrungDT (FUHN) MAD101 Chapter 4 10 / 18
Example 3. Recursive definition for the set of full binary trees.
Basic step: A single vertex is a full binary tree.
Recursive step: If T1 and T2 are two full binary trees then there is a
full binary tree, denoted by T1 .T2 , consisting of a root r together
with edges connecting this root to the root of the left subtree T1 and
the root of the right subtree T2 .
TrungDT (FUHN) MAD101 Chapter 4 10 / 18
TrungDT (FUHN) MAD101 Chapter 4 11 / 18
Example 4. Give a recursive definition for:
TrungDT (FUHN) MAD101 Chapter 4 11 / 18
Example 4. Give a recursive definition for:
(a) Leaves of full binary trees.
TrungDT (FUHN) MAD101 Chapter 4 11 / 18
Example 4. Give a recursive definition for:
(a) Leaves of full binary trees.
(b) Height of full binary trees.
TrungDT (FUHN) MAD101 Chapter 4 11 / 18
Example 4. Give a recursive definition for:
(a) Leaves of full binary trees.
(b) Height of full binary trees.
TrungDT (FUHN) MAD101 Chapter 4 11 / 18
Structural Induction
TrungDT (FUHN) MAD101 Chapter 4 12 / 18
Structural Induction
Let S be a set defined recursively.
TrungDT (FUHN) MAD101 Chapter 4 12 / 18
Structural Induction
Let S be a set defined recursively. To prove that a property P is true for
all elements of S we can use structural induction.
TrungDT (FUHN) MAD101 Chapter 4 12 / 18
Structural Induction
Let S be a set defined recursively. To prove that a property P is true for
all elements of S we can use structural induction.
Basic step: Prove that P is true for elements of S defined in the basic
step.
TrungDT (FUHN) MAD101 Chapter 4 12 / 18
Structural Induction
Let S be a set defined recursively. To prove that a property P is true for
all elements of S we can use structural induction.
Basic step: Prove that P is true for elements of S defined in the basic
step.
Recursive step: Show that if the property P is true for the elements
used to construct new elements in the recursive step of the definition
of S, then the property P is also true for these new elements.
TrungDT (FUHN) MAD101 Chapter 4 12 / 18
TrungDT (FUHN) MAD101 Chapter 4 13 / 18
Example 1.
TrungDT (FUHN) MAD101 Chapter 4 13 / 18
Example 1. Let T be a full binary tree with the number of vertices n(T )
and the number of leaves l(T ). Prove that n(T ) = 2l(T ) − 1.
TrungDT (FUHN) MAD101 Chapter 4 13 / 18
Example 1. Let T be a full binary tree with the number of vertices n(T )
and the number of leaves l(T ). Prove that n(T ) = 2l(T ) − 1.
Example 2. Let T be a full binary tree with the number of vertices n(T )
and the height h(T ). Prove that n(T ) ≤ 2h(T )+1 − 1.
TrungDT (FUHN) MAD101 Chapter 4 13 / 18
Example 1. Let T be a full binary tree with the number of vertices n(T )
and the number of leaves l(T ). Prove that n(T ) = 2l(T ) − 1.
Example 2. Let T be a full binary tree with the number of vertices n(T )
and the height h(T ). Prove that n(T ) ≤ 2h(T )+1 − 1.
TrungDT (FUHN) MAD101 Chapter 4 13 / 18
Generalized Induction
TrungDT (FUHN) MAD101 Chapter 4 14 / 18
Generalized Induction
Example.
TrungDT (FUHN) MAD101 Chapter 4 14 / 18
Generalized Induction
Example.
Given the sequence {am,n } defined recursively as follows:
TrungDT (FUHN) MAD101 Chapter 4 14 / 18
Generalized Induction
Example.
Given the sequence {am,n } defined recursively as follows:
a0,0 = 0, and
TrungDT (FUHN) MAD101 Chapter 4 14 / 18
Generalized Induction
Example.
Given the sequence {am,n } defined recursively as follows:
a0,0 = 0,
and
am−1,n + 1 if n = 0 và m > 0,
am,n =
am,n−1 + n if n > 0
TrungDT (FUHN) MAD101 Chapter 4 14 / 18
Generalized Induction
Example.
Given the sequence {am,n } defined recursively as follows:
a0,0 = 0,
and
am−1,n + 1 if n = 0 và m > 0,
am,n =
am,n−1 + n if n > 0
Prove that am,n = m + n(n + 1)/2 for all m, n ≥ 0.
TrungDT (FUHN) MAD101 Chapter 4 14 / 18
4.4 Recursive Algorithms
TrungDT (FUHN) MAD101 Chapter 4 15 / 18
4.4 Recursive Algorithms
An algorithm is called recursive if it solves a problem by reducing it to an
instance of the same problem with smaller input
TrungDT (FUHN) MAD101 Chapter 4 15 / 18
4.4 Recursive Algorithms
An algorithm is called recursive if it solves a problem by reducing it to an
instance of the same problem with smaller input
Example 1. A recursive algorithm that computes 5n for n ≥ 0.
TrungDT (FUHN) MAD101 Chapter 4 15 / 18
4.4 Recursive Algorithms
An algorithm is called recursive if it solves a problem by reducing it to an
instance of the same problem with smaller input
Example 1. A recursive algorithm that computes 5n for n ≥ 0.
Procedure power (n: non-negative)
if n = 0 then power (0) := 1
else power (n) := power (n − 1) ∗ 5
TrungDT (FUHN) MAD101 Chapter 4 15 / 18
TrungDT (FUHN) MAD101 Chapter 4 16 / 18
Example 2. Write a recursive algorithm to compute n!.
TrungDT (FUHN) MAD101 Chapter 4 16 / 18
Example 2. Write a recursive algorithm to compute n!.
Example 3. Write a recursive algorithm to compute the greatest common
divisor of two non-negative integers.
TrungDT (FUHN) MAD101 Chapter 4 16 / 18
Example 2. Write a recursive algorithm to compute n!.
Example 3. Write a recursive algorithm to compute the greatest common
divisor of two non-negative integers.
Example 4. Express the linear search algorithm by a recursive procedure .
TrungDT (FUHN) MAD101 Chapter 4 16 / 18
Example 2. Write a recursive algorithm to compute n!.
Example 3. Write a recursive algorithm to compute the greatest common
divisor of two non-negative integers.
Example 4. Express the linear search algorithm by a recursive procedure .
Example 5. Express the binary search algorithm by a recursive procedure.
TrungDT (FUHN) MAD101 Chapter 4 16 / 18
Example 2. Write a recursive algorithm to compute n!.
Example 3. Write a recursive algorithm to compute the greatest common
divisor of two non-negative integers.
Example 4. Express the linear search algorithm by a recursive procedure .
Example 5. Express the binary search algorithm by a recursive procedure.
TrungDT (FUHN) MAD101 Chapter 4 16 / 18
Recursion and Iteration
TrungDT (FUHN) MAD101 Chapter 4 17 / 18
Recursion and Iteration
Problem. Write a recursive algorithm and an iteration algorithm to
compute the nth Fibonacci number, and compare their complexity via the
number of additions used.
TrungDT (FUHN) MAD101 Chapter 4 17 / 18
Recursion and Iteration
Problem. Write a recursive algorithm and an iteration algorithm to
compute the nth Fibonacci number, and compare their complexity via the
number of additions used.
TrungDT (FUHN) MAD101 Chapter 4 17 / 18
Recursion and Iteration
Problem. Write a recursive algorithm and an iteration algorithm to
compute the nth Fibonacci number, and compare their complexity via the
number of additions used.
Procedure Iterative Fib (n)
if n = 0 then y := 0
else
x:=0
y:=1
for i := 1 to n − 1 do
z:=x+y
x:=y
y:=z
Print(y )
TrungDT (FUHN) MAD101 Chapter 4 17 / 18
Recursion and Iteration
Problem. Write a recursive algorithm and an iteration algorithm to
compute the nth Fibonacci number, and compare their complexity via the
number of additions used.
Procedure Iterative Fib (n) Procedure Fib (n)
if n = 0 then y := 0 if n = 0 then Fib(0) := 0
else else if n = 1 then Fib(1) := 1
x:=0 else
y:=1 Fib(n) := Fib(n − 1) + Fib(n − 2)
for i := 1 to n − 1 do
z:=x+y
x:=y
y:=z
Print(y )
TrungDT (FUHN) MAD101 Chapter 4 17 / 18
Merge Sort Algorithm
TrungDT (FUHN) MAD101 Chapter 4 18 / 18
Merge Sort Algorithm
Procedure mergesort (L = a1 , a2 , . . . , an )
if n > 1 then
m := bn/2c
L1 = a1 , a2 , . . . , am
L2 = am+1 , am+2 , . . . , an
L := merge(mergesort(L1 ), mergersort(L2 ))
Print (L)
TrungDT (FUHN) MAD101 Chapter 4 18 / 18
Merge Sort Algorithm
Procedure mergesort (L = a1 , a2 , . . . , an )
if n > 1 then
m := bn/2c
L1 = a1 , a2 , . . . , am
L2 = am+1 , am+2 , . . . , an
L := merge(mergesort(L1 ), mergersort(L2 ))
Print (L)
Theorem
TrungDT (FUHN) MAD101 Chapter 4 18 / 18
Merge Sort Algorithm
Procedure mergesort (L = a1 , a2 , . . . , an )
if n > 1 then
m := bn/2c
L1 = a1 , a2 , . . . , am
L2 = am+1 , am+2 , . . . , an
L := merge(mergesort(L1 ), mergersort(L2 ))
Print (L)
Theorem
The number of comparisons needed to merge sort a list of n elements is
O(n log n).
TrungDT (FUHN) MAD101 Chapter 4 18 / 18
