Report

Chapter 8 Recursion 8.1 Recursively Defined Sequences Recursion • A Sequence can be defined as: – informally be providing a few terms to demonstrate the pattern, i.e. 3, 5, 7, …. – give an explicit formula for it nth term, i.e. n an 1 n 1 – or, by recursion which requires a recurrence relation. Defining Recursion • Recursion requires • recurrence relation relates later terms in the sequence to earlier terms and • initial conditions, values of the first few terms of the sequence. – Example b0, b1, b2, … For all integers k>= 2, 1. bk = bk-1 + bk-2 (recurrence relation) 2. b0 = 1, b1 = 3 (initial conditions) b2 = b2-1 + b2-2 = b1 + b0 = 3 + 1 = 4 b3 = b3-1 + b3-2 = b2 + b1 = 4 + 3 = 7 b5 = b5-1 + b5-2 = b4 + b3 = 11 + 7 = 18 Recursion • Definition: – A recurrence relation for a sequence a0, a1, a2,… is a formula that relates each term ak to ceratin of its predecessors ak-1, ak-2, … , ak-I, where I is an integer and k is any integer greater than or equal to i. – The initial conditions for such a recurrence relation specify the values of a0, a1, a2,…,ai-1, if I is a fixed integer, or a0, a1, a2,…,am, where m is an integer with m>=0, if i depends on k. Example • Computing terms – Recursive sequence ck, for all integers k >=2, find c2, c3, c4 1. ck = ck-1 + k ck-2 + 1 (recurrence relation) 2. c0 = 1 and c1 = 2 (initial conditions) c2 = c2-1 + 2*c2-2 + 1 = c1 + 2*c0 + 1 = 2 + 2*1 + 1 = 5 c3 = c3-1 + 3*c3-2 + 1 = c2 + 3*c1 + 1 = 5 + 3*2 + 1 = 12 c4 = c4-1 + 4*c4-2 + 1 = c3 + 4*c2 + 1 = 10 + 4*12 + 1 = 59 Equivalent Recursion • There is more than one way to setup a recursive sequence! – for all k>=1, sk = 3sk-1 – 1 – for all k>=0, sk+1 = 3sk – 1 • Are the two sequences equivalent? – show the results of the sequence for terms: • starting at k = 1: s1 = 3s0 – 1, s2 = 3s1 – 1, s3 = 3s2 – 1 • starting at k = 0: s0+1 = 3s0 – 1, s1+1 = 3s1 – 1, … – change first term to second by adjusting first k • for all k>=1, sk = 3sk-1 – 1 => k start at 0 (k≥0) sk+1 =3sk – 1 • same as the second form. Example • Show that sequence given satisfies a recurrence relation: – 1, -1!, 2!, -3!, 4!, …, (-1)nn!, …, for n≥0 is equivalent to sk = (-k)sk-1 for k≥1 – General term of the seq sn starting with s0 = 1, then sn = (1)nn! for n≥0 • substitute for k and k-1: sk = (-1)kk! , sk-1 = (-1)k-1(k-1)! (-k)sk-1 = (-k)[(-1)k-1(k-1)!] (sk defined above) = (k)(-1)(-1)k-1(k-1)! = (k)(-1)k(k-1)! = (-1)k(k)(k-1)! = (-1)k k! = sk Solving Recursive Problems • To solve a problem recursively means to find a way to break it down into smaller subproblems each having the same form as the original problem. Towers of Hanoi • Problem statement: eight disks with holes in the center that are stacked from largest diameter to smallest on the first of three poles. Move the stacked disk from one pole to another. • Rules: a larger disk cannot be placed on top of a smaller disk at any time. Towers of Hanoi • Recursive Solution 1. 2. 3. Transfer the top k-1 disks from pole A to pole B. (Note: k>2 requires a number of moves.) Move the bottom disk from pole A to pole C. Transfer the top k-1 disks from pole B to pole C. (Again, if k>2, execution of this step will require more than one move.) Towers of Hanoi min moves to transfer a tower of k disks from A to C = min num of moves to go from position a to position b + min num of moves to go from position b to position c + min num of moves to go from position c to position d For each integer n≥1, mn = min num of moves to transfer a tower of n disks from one pole to another. position a to position b = mk-1, position b to c = 1 move, position c to position d = mk-1 moves. mk = mk-1 + 1 + mk-1 = 2mk-1 + 1, integers k≥2 initial condition: m1 = [move one disk to another pole] = 1 Towers of Hanoi 1. mk = 2mk-1 + 1 (recurrence relation) 2. m1 = 1 (initial condition) m2 = 2m1 + 1 = 3 m3 = 2m2 + 1 = 7 m4 = 2m3 + 1 = 15 … m6 = 2m5 + 1 = 63 Fibonacci • Leonardo of Pisa was the greatest mathematician of the 13th century. • Proposed the following problem: – A single pair of rabbits (male/female) is born at the beginning of a year. Assuming the following conditions: 1. Rabbit pairs are not fertile during their first month of life but thereafter give birth to one new male/female pair at the end of every month. 2. No rabbits die – How many rabbits will there be at the end of the year? Fibonacci • To solve the problem you can hand compute for each of the 12 months. – m1 = 1, m2 = 1, m3 = 2, m4 = 3, m5 = 5, … m11 = 144, m12 = 233 num of pairs alive at end of month k = num of pairs alive at end of month k-1 = num of pairs alive at month k-1 + num of pairs born at end of month k + num of pairs alive at month k-2 Fibonacci – – – – for n ≥1, Fn= num of pairs alive at month n F0 = the initial number of pairs F0 = 1 Fk = Fk-1 + Fk-2 • Fibonacci Sequence 1. Fk = Fk-1 + Fk-2 (recurrence relation) 2. F0 = 1, F1 = 1 (initial condition) F2 = F1 + F0 = 1+1 = 2 F3 = F2 + F1 = 2+1 = 3 F4 = F3 + F2 = 3+2 = 5 … F12 = F11 + F10 = 144 + 89 = 233 Compound Interest • Compute compound interest on principle value using recursive sequence. • $100,000 principle, earning 4% per year, how much would you have in 21 years. amt in account end of a year = amt in account at end of previous year = amt in account at end of previous year + interest earned on account during year + (0.04)* amt in account previous year An = amt in account at end of year n A0 = initial amount (principle) Ak = Ak-1 + (0.04)*Ak-1 Ak = (1.04)*Ak-1 Compound Interests • Compounding multiple times a year – interest is broken up of over the year based on the number of compounding periods – example 3% compounded quarterly • 3%/4 = .03/4 = 0.0075 (interest rate per period) • interest earned during kth period = Pk-1(i/m) • Pk = Pk-1 + Pk-1 (i/m) = Pk-1(1 + i/m) Example • Given $10,000, How much will the account be work at the end of one year with a interest rate of 3% compounded quarterly? – Pk = Pk-1 (1+0.0075) = Pk-1(1.0075), integers k≥1 – P0 = 10,000 – P1 = 1.0075*P0=1.0075*10,000 =10,075.00 – P2 = 10,150.56 – P3 = 10,226.69 – P4 = 10,303.39