Recursion

1

Gongjun Yan

RECURSION (TEXTBOOK: §4.3, §4.4) 2008/10/29

§4.3: Recursive Definitions 2



A recursive definition of a set always consists of three distinct clauses: The basis clause (or simply basis) establishes that certain objects are in the set.  The inductive clause (or simply induction) establishes the ways in which elements of the set can be combined to produce new elements of the set.  The extremal clause asserts that unless an object satisfying basis clause and inductive clause, the object is not a member of the set. 

2008/10/29

Example 1 3

 

Examples of Recursive Definition of Set Example 1. Definition of the Set of Natural Numbers The set N is the set that satisfies the following three clauses: Basis Clause: 0  N Inductive Clause: For any element x in N, x + 1 is in N. Extremal Clause: Nothing is in N unless it is obtained from the Basis and Inductive Clauses. Set Theory

29 October 2008

Example 2 4



Example 2. Definition of the Set of Even Integers The set EI is the set that satisfies the following three clauses: Basis Clause: 0  EI Inductive Clause: For any element x in EI, x + 2, and x - 2 are in EI. Extremal Clause: Nothing is in EI unless it is obtained from the Basis and Inductive Clauses. 29 October 2008

Tips 5





Tips for recursively defining a set: For the "Basis Clause", try simplest elements in the set such as smallest numbers (0, or 1), simplest expressions, or shortest strings. Then see how other elements can be obtained from them, and generalize that generation process for the "Inductive Clause". Game Time

29 October 2008

generalized union 6

Set Theory

29 October 2008

Recursive Definition of Function 7



Some functions can also be defined recursively. Condition: The domain of the function you wish to define recursively must be a set defined recursively. How to define function recursively:  First

the values of the function for the basis elements of the domain are specified.  Then the value of the function at an element, say x, of the domain is defined using its value at the parent(s) of the element x. 29 October 2008

Example 8



Example 3: The function f(n) = n! for natural numbers n can be defined recursively as follows:  Basis

Clause: f(0) = 0! = 1  Inductive Clause: For all natural number n, f(n+1) = (n+1) f(n). 

Using this definition, 3! can be found as follows: Since 0 ! = 1, 1 ! = 1 * 0 ! = 1 * 1 = 1 , Hence 2 ! = 2 * 1 ! = 2 * 1 = 2 . Hence 3 ! = 3 * 2 ! = 3 * 2 * 1 = 6 .

 29 October 2008

Extremal Clause 9

 

 

Note that here Extremal Clause is not necessary because the set of natural numbers can be defined recursively that has the extremal clause in it. So there is no chance of other elements to come into the function being defined.

29 October 2008

Examples 10





Example 4: The function f(n) = 2n for natural numbers n can be defined recursively as follows: Basis Clause: f(0) = 1 Inductive Clause: For all natural number n, f(n+1) = 2 f(n) . Example 5: The function f(n) = 2n + 1 for natural numbers n can be defined recursively as follows:  Basis

Clause: f(0) = 1  Inductive Clause: For all natural number n, f(n+1) = f(n) + 2 . 29 October 2008

More examples 11



Example 6: The function L from the set S of strings over {a, b} to the set of natural numbers that gives the length of a string can be defined recursively as follows: Basis Clause: For symbols a and b of the alphabet, L(a) = 1 and L(b) = 1. Inductive Clause: For any string x and y of S, L(xy) = L(x) + L(y) , where xy is the concatenation of strings x and y. 29 October 2008

The Fibonacci Series 12



The Fibonacci series fn≥0 is a famous series defined by: f0 :≡ 0, f1 :≡ 1, fn≥2 :≡ fn−1 + fn−2 0 1 1 2 3 58 13

2008/10/29

Tree Structures --- Rooted Trees 13

  



The set of rooted trees Root 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. 2008/10/29

Examples of Rooted Trees 14

2008/10/29

Tree Structures --- Binary Trees 15



The set of extended binary trees can be defined recursively by these steps:  BASIS

STEP: A 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, containing 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.

2008/10/29

Example of Extended Binary Trees 16

2008/10/29

Recursive Algorithms (§4.4) 17





Recursive definitions can be used to describe algorithms as well as functions and sets. Example: A procedure to compute an. procedure power(a≠0: real, nN) if n = 0 then return 1 else return a · power(a, n−1) 2008/10/29

Efficiency of Recursive Algorithms 18





The time complexity of a recursive algorithm may depend critically on the number of recursive calls it makes. Example: Modular exponentiation to a power n can take log(n) time if done right, but linear time if done slightly differently.  Task:

Compute bn mod m, where m≥2, n≥0, and 1≤b<m.

2008/10/29

Modular Exponentiation Alg. #1 19

Uses the fact that bn = b·bn−1 and that x·y mod m = x·(y mod m) mod m. (Prove the latter theorem at home.) procedure mpower(b≥1,n≥0,m>b N) {Returns bn mod m.} if n=0 then return 1 else return (b·mpower(b,n−1,m)) mod m Note this algorithm takes Θ(n) steps!

2008/10/29

Modular Exponentiation Alg. #2 20

Uses the fact that b2k = bk·2 = (bk)2. procedure mpower(b,n,m) {same signature} if n=0 then return 1 else if 2|n then return mpower(b,n/2,m)2 mod m else return (mpower(b,n−1,m)·b) mod m What is its time complexity? 

Θ(log n) steps

2008/10/29

A Slight Variation 21

Nearly identical but takes Θ(n) time instead! procedure mpower(b,n,m) {same signature} if n=0 then return 1 else if 2|n then return (mpower(b,n/2,m)· mpower(b,n/2,m)) mod m else return (mpower(b,n−1,m)·b) mod m The number of recursive calls made is critical. 2008/10/29

Recursive Euclid’s Algorithm 22

Compute Greatest common divisor procedure gcd(a,bN) if a = 0 then return b else return gcd(b mod a, a)   

Example: gcd(5,8) = gcd(8%5,5)=gcd(3,5)= gcd(5%3,3) = gcd(2,3) = gcd(3%2,2) = gcd(1,2) =gcd(2%1,1)=gcd(0,1) = 1 2008/10/29

Sequential Search 23



Input: L is an array, i and j are positive integers, i j, and x is the key to be searched for in L. Output: If x is in L between indexes i and j, then output its index, else output 0. Algorithm: if i j , then { if L(i) = x, then return i ; else return SeqSearch(L, i+1, j, x) } else return 0. 29 October 2008

Ackermann’s Function 24



Find the value A(1,0), A(0,1), A(1,1), and A(2,2) according to the following recursive definition.

2 n 0  Am.n    2   Am  1, A(m, n  1) 

if m  0 if m  1 and n  0 if m  1 and n  1 if m  1 and n  2

2008/10/29

Game Time 25



Game Time

29 October 2008