RecursionSlide 2factoroial (n)Defining factorial(n)Slide 5Implementing factorial(n) (edit)Implementing factorial(n) (edited)Implementing factorial(n)Slide 9General form of Recursive MethodRecursion Vs Loops (Iteration)Tracing Recursive CallsSlide 13Recursion PitfallsSlide 15Recursive MethodsRecursive Functions with Multiple ParametersRecursive Functions with Multiple Parameters (edit)Recursive Functions with Multiple Parameters (edited)Slide 20Defining power(base, exponent)Recursive Procedures: greet(n)Defining greet(n) (edit)Defining greet(n) (edited)Defining greet(n)Slide 26Implementing greet(n) (edit)Implementing greet(n) (edited)Implementing greet(n)List-based recursion: multiplyList()List-based recursion: multiplyList() (edited)Slide 32Tracing multiplyList()Recursion•English–Return (Oxford/Webster)–procedure repeating itself indefinitely or until condition met, such as grammar rule (Webster) •adequate: satisfactory•satisfactory: adequate–recursion: recursion•Mathematics–expression giving successive terms of a series (Oxford)•Programming–Method calling itself.–On a smaller problem.–Alternative to loops.Recursion• Recursive Functions• Recursive Procedures• Number-based Recursion• List-based Recursionfactoroial (n)public static int factorial (int n) { int product = 1; while (n > 0) { product *= n; n -= 1; } return product; }public static void main (String[] args) {while (true) {// loop condition never falseint n = Keyboard.readInt();if (n < 0) break;System.out.println(“factorial =“ + factorial(n);} }1*2*3*4 … nDefining factorial(n)Product of the first n numbers.1*2*3*4 … nfactorial (0) = 1factorial (1) = 1 = 1* factorial(0)factorial (2) = 2*1 = 2* factorial(1)factorial (3) = 3*2*1 = 3* factorial(2)factorial (4) = 4*3*2*1 = 4* factorial(3)factorial (n) = n*n-1*..*1 = n* factorial(n-1)Defining factorial(n)factorial (n) = 1factorial (n) = n* factorial(n-1)if n == 0if n > 0Implementing factorial(n) (edit)factorial (n) = 1factorial (n) = n* factorial(n-1)if n == 0if n > 0public static int factorial (int n) { ??? }Implementing factorial(n) (edited)factorial (n) = 1factorial (n) = n* factorial(n-1)if n == 0if n > 0public static int factorial (int n) { if (n == 0) return 1; if (n > 0) return n*factorial(n-1); }Implementing factorial(n)factorial (n) = 1factorial (n) = n* factorial(n-1)if n == 0if n > 0public static int factorial (int n) { if (n == 0)return 1; if (n > 0)return n*factorial(n-1); }Function must return something for all casesn < 0 ?Implementing factorial(n)factorial (n) = 1factorial (n) = n* factorial(n-1)if n == 0if n > 0public static int factorial (int n) { if (n == 0)return 1; else if (n < 0)return factorial(-n); elsereturn n*factorial(n-1); }Recursive reduction stepsBase casefactorial (n) = - factorial(n) if n < 0General form of Recursive Methodif (base case 1 ) return solution for base case 1else if (base case 2) return solution for base case 2….else if (base case n) return solution for base case nelse if (recursive case 1) do some preprocessing recurse on reduced problem do some postprocessing…else if (recursive case m) do some preprocessing recurse on reduced problem do some postprocessingRecursion Vs Loops (Iteration)public static int factorial (int n) { if (n == 0)return 1; else if (n < 0)return factorial(-n); elsereturn n*factorial(n-1); }public static int factorial (int n) { int product = 1; while (n > 0) { product *= n; n -= 1; } return product; }Implementation follows from definition.Tracing Recursive CallsStackTracing Recursive CallsInvocation n return valuefactorial(1) 1 ?factorial(2) 2 ?Invocation n return valuefactorial(0) 0 ?factorial(1) 1 ?factorial(2) 2 ?Invocation n return valuefactorial(0) 0 1factorial(1) 1 ?factorial(2) 2 ?Invocation n return valuefactorial(0) 0 1factorial(1) 1 1factorial(2) 2 ?Invocation n return valuefactorial(0) 0 1factorial(1) 1 1factorial(2) 2 2Recursion Pitfallspublic static int factorial (int n) { return n*factorial(n-1); }factorial (2)2* factorial (1)1* factorial (0)0* factorial (-1)-1 * factorial(-2)Infinite recursion! (Stack overflow)No base case....Recursion Pitfallsfactorial (2)factorial (3) / 3factorial (4) / 4factorial (5) / 5factorial(6) / 6Infinite recursion!Recurses on bigger problem....public static int factorial (int n) { if (n == 0)return 1; else if (n < 0)return factorial(-n); elsereturn factorial(n+1)/n+1; }Recursive Methods•Should have base case(s)•Recurse on smaller problem(s) - recursive calls should converge to base case(s)Recursive Functions with Multiple Parameterspower (base, exponent)base*base*base*…*basepower (0, exponent) = 0exponent # of timesbaseexponentpower (1, exponent) = 1power (2, exponent) = 2*2*2…*2 (exponent times)power (3, exponent) = 3*3*3…*3 (exponent times)No pattern!Recursive Functions with Multiple Parameters (edit)power (base, exponent)base*base*base*…*baseexponent # of timesbaseexponent?????Recursive Functions with Multiple Parameters (edited)power (base, exponent)base*base*base*…*baseexponent # of timesbaseexponentpower(base, 0) = 1power(base, 1) = base * 1 = base*power(base, 0)power(base, 2) = base*base*1 = base* power(base, 1)power(base,exponent) = base*power(base, exponent-1)Recursive Functions with Multiple Parameterspower (base, exponent)base*base*base*…*baseexponent # of timesbaseexponentpower (base, 0) = 1power (base, 1) = base*1 = base* power(base, 0)power (base, 2) = base*base*1 = base* power(base, 1)power (base, exponent) = base*power(base, exponent-1)Defining power(base, exponent)power (base, exponent) = 1 if exponent <= 0power (base, exponent) = base*power(base, exponent-1) if exponent <= 0public static int power (int base, exponent) { if (n <= 0)return base; else return base*power(base, exponent-1); }Recursive Procedures: greet(n)greet (1)print “hello”greet (0) greet (2) greet(n)n timesprint “hello”print “hello”print “hello”print “hello”print “hello”print “hello”Defining greet(n) (edit)greet (1)print “hello”greet (0) greet (2) greet(n)n timesprint “hello”print “hello”print “hello”print “hello”print “hello”print “hello”Defining greet(n) (edited)greet (1)print “hello”greet (0) greet (2) greet(n)n timesprint “hello”print “hello”print “hello”print “hello”print “hello”print “hello”Do