Theory Review: (5 Minutes) Recursion: Recursion is a type of divide-and-conquer technique used to solve difficult programming problems by reducing a problem to simpler, but identical,"sub-problems." The sub-problems are then reduced to "sub-sub-problems." This multi-step reduction process continues until a trivial case (called base case) is reached. The solutions to each sub-problem, starting with the trivial case solution(s) at the lowest level and working upward to the final solution to the original problem, are then combined to produce solutions to the next higher level of problems. When to use recursive algorithms: Problems that can be solved using a recursive solution must have the following two characteristics: 1. The problem must be able to be stated in terms of simpler yet identical sub-problems. 2. There must be a trivial case (base case) that is easily solved. Example (from theory): Raising a number to an arbitrary power. Solution by dividing problem into its sub-problem: Suppose we want to find some base 'b' raised to some power 'e' i.e. b For example, if b=2 and e=5, then b = 25 = 32. In order to find 2, we can use the following procedure: 23 = 2*2*2*2*2 (2 is multiplied with itself 5 times) It can also be reduced to its sub-problem as 25 = 2*24 Now 2* can be further reduced to its sub-problem as 24 = 2*23 Now 2 can be further reduced to its sub-problem as 23 = 2*22 Now 22 can be further reduced to its sub-problem as 22 = 2*2! Now 2' can be further reduced to its sub-problem as 2 = 2*29 Now the sub-problem 2 cannot be further reduced. So, it becomes our base case i.e. when power becomes equal to 0, we should get 1. Recursive Solution: In order to find the recursive definition of this problem, we will give 'b' and 'e' as an input to our recursive method. Then after every step, we shall reduce the power by 1 in order to come closer to the base case. When we reach base case, we should return 1. Recursive code for the method Raising a number to an arbitrary power" is as follows: public static int power(int b, int e) { if (c=0) return 1; else return b*power(b, e-1)