IN JAVA (PLEASE CODE ALL 3 PROGRAMS)

Part I Climbing the stairs (15 points) Problem description: You need to write a recursive function int climbingStairs(int n). This function takes only one parameter n. Suppose that youre climbing a staircase with n stairsteps. Each time you can choose to climb either 1 step or 2 steps. Your function shall return the total distinct ways in which you can climb to the top. Sample input/output: Input 2 Output 2 Explanation There are two ways to climb to the top: 1. 1 step + 1 step 2. 2 steps Input 3 Output 3 Explanation There are three ways to climb to the top: 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step

Part II Greatest Common Divisor (15 points) Problem description: You need to write a recursive function int gcd (int num1, int num2). This function takes two ints as parameters num1 and num2. Your function shall return the greatest common divisor of num1 and num2. If either num1 or num2 is negative or 0, return -1. Sample input/output: Input 24, 36 Output 12 Input 7, 5 Output 1 Input 0, 2 Output -1

Part III Binary Search (20 points) Problem description: You need to write a recursive function int binarySearch(int[]array, int target, int left, int right). The function takes four parameters: a sorted int array, a target number, left index, and right index. The sorted int array contains only positive integers, with each integer appear only once. Your job is to use binary search to locate the index of target. The left index and right index are just for your convenience when using recursion. Return -1 if you cant find the target. You may assume that the first input of int left and int right will always be 0 and array.length-1, respectively. Sample input/output: Input Array: [1, 2, 3, 5, 6, 8, 13] left: 0 right: 6 Target: 3 Output 2 Explanation: The index of 3 is 2 Input Array: [1, 2, 3, 7, 8] left: 0 right: 4 Target: 5 Output -1 Explanation: 5 is not in this array Input Array: [] left: 0 right: -1 Target: 12 Output -1 Explanation: The array is empty. Thus 12 cannot be found