CPSC 2430 Data Structure

Winter Quarter 2022

Lab 2 Due: 11:59pm, Jan 24

Lab 2 focuses on time recursion design and complexity analysis and. In this lab, you will rewrite your Lab 1 program in a recursive approach and compare the time complexity between different implementations and explain what causes the difference using Big O notation.

Task 1: Rewrite your Lab 1 function bico(int x, int y) using recursions. Your bico(int x, int y) should still have two parameters: the first one is the degree of binomial expression, and the second parameter is the i^thcoefficient. For example, bico(4,2) should return 6 because

Like Lab 1, you also need to provide a user interface:

Output

Unlike Lab 1, your solution for finding the coefficient (the construction for Pascals triangle) should be implemented with recursion.