Consider three sequences of integers defined recursively as follows:
A0 = 0 A1 = 1 An = A[n/2] + Bn - 3Cn-2 for n >= 2 B0 = 1 Bn = n - 2B[n/3] + Cn for n >= 1 C0 = -1 C1 = 0 C2 = 1 Cn = 5 - An-1 + Bn-2 - Cn-3 for n >= 3Here for a real number x the notation [x] stands for the largest integer less than or equal to x. For example, [3]=3, [3.1416]=3, [0.1416]=0, [-1.1416]=-2, [-3]=-3, [5/3]=1, [-5/3]=-2, etc. For this exercise you need consider x>=0 only, in which case [x] can be viewed as the integral part of x.
Part I
Write three mutually recursive functions for computing An, Bn and Cn.
Compute A25. Count the total number of times Ai, Bi and Ci are computed for i=0,...,25 (that is, the corresponding functions are called with argument i) during the computation of A25.
Compute B25. Count the total number of times Ai, Bi and Ci are computed for i=0,...,25 during the computation of B25.
Compute C25. Count the total number of times
Ai, Bi and Ci are computed
for i=0,...,25 during the computation of C25.
Part II
Part I illustrates that the functions are called multiple times on the same argument. The number of calls in some cases is intolerably large. This can be remedied by avoiding recursion as follows.
Write an iterative version of the mutually recursive procedure. Maintain three arrays a, b and c each of size 26. Use the boundary conditions (values for A0, A1, B0 etc.) to initialize. Then use the recursive definition to update the A, B and C values ``simultaneously''. In this method if some value (say, Ai) is once computed, it is stored in the appropriate array location for all subsequent uses. This saves the time for recalculating the same value again and again.
Compute the values A25, B25 and C25 using the iterative procedure.
Typical output
The recommended format of the output for computing A10, B10 and C10 is as follows:
Recursive method : A(10)=37 Number of calls: A( 0): 0 A( 1): 203 A( 2): 145 A( 3): 58 A( 4): 26 A( 5): 12 A( 6): 6 A( 7): 3 A( 8): 1 A( 9): 1 A(10): 1 B( 0): 455 B( 1): 246 B( 2): 209 B( 3): 84 B( 4): 37 B( 5): 18 B( 6): 9 B( 7): 4 B( 8): 2 B( 9): 1 B(10): 1 C( 0): 252 C( 1): 353 C( 2): 259 C( 3): 107 C( 4): 49 C( 5): 24 C( 6): 11 C( 7): 6 C( 8): 3 C( 9): 1 C(10): 1 B(10)=3 Number of calls: A( 0): 0 A( 1): 159 A( 2): 113 A( 3): 46 A( 4): 20 A( 5): 9 A( 6): 5 A( 7): 2 A( 8): 1 A( 9): 1 A(10): 0 B( 0): 357 B( 1): 193 B( 2): 164 B( 3): 66 B( 4): 29 B( 5): 14 B( 6): 7 B( 7): 3 B( 8): 2 B( 9): 1 B(10): 1 C( 0): 197 C( 1): 278 C( 2): 202 C( 3): 84 C( 4): 39 C( 5): 18 C( 6): 9 C( 7): 5 C( 8): 2 C( 9): 1 C(10): 1 C(10)=3 Number of calls: A( 0): 0 A( 1): 158 A( 2): 112 A( 3): 46 A( 4): 20 A( 5): 9 A( 6): 5 A( 7): 2 A( 8): 1 A( 9): 1 A(10): 0 B( 0): 354 B( 1): 191 B( 2): 163 B( 3): 65 B( 4): 29 B( 5): 14 B( 6): 7 B( 7): 3 B( 8): 2 B( 9): 1 B(10): 0 C( 0): 195 C( 1): 276 C( 2): 201 C( 3): 83 C( 4): 39 C( 5): 18 C( 6): 9 C( 7): 5 C( 8): 2 C( 9): 1 C(10): 1 Iterative method : a(10)=37, b(10)=3, c(10)=3.
[Course home] [Home]