we are required to write a program in python which generates a nth Pell number using Recursion and Memoization. Please help me as soon as possible A Pell number (nth Pell number is represented as P (n)) is recursively defined as: 0 if n = 0; Pn = 1 if n = 1; 2Pn−1 + Pn−2 otherwise. The above function when expanded, gives rise to the series: 0,1,2,5,12,29,70,169, 408 ... The zeroth Pell number P (0) is 0, first Pell number P (1) is 1, sixth Pell number P (6) is 70 etc. To find nth Pell number using a computer program, one of the technique used is recursive generation. But using recursion alone is not an efficient way to generate a Pell number. Consider the following recursion tree: 2 P (5) 2P (4) 2P (3) P (3) P (2) 2P (2) P (1) To calculate P (4), P (3) and P (2) is computed. To calculate P (3), P (2) and P (1) is computed. But as you observe, P (2) is computed again. This is a repeated computation. This repeated computation is avoided by storing already computed P (k) value in a data structure and using that value to compute other Pell numbers. This technique is called Memoization. Your task is to write a program to generate P (n) using Recursion and Mem- oization. Your program should compute l Pell numbers for which the input and output format is as follows: • The first line will contain l cases. • The next l lines will have the value of n in each line for which P (n) has to be computed. For your program, 10 <= n <= 10000 • The output should output a P (n) for each n in a new line. For example: INPUT 3 3 5 6 OUTPUT 5 29 70
--
