Recursion.md (2416B)
1 +++ 2 title = 'Recursion' 3 +++ 4 # Recursion 5 Recursion: when a method calls itself…how would you use that? will explain, let’s start with something everyone here knows 6 7 Used for quicksort and divide and conquer algorithms. 8 Divide and conquer: 9 1. Divide problem into smaller ones 10 2. Compute subproblems recursively 11 3. Combine partial results to overall solution 12 13 ## Factorial — n! 14 Everyone here knows what the factorial is. 15 16 Important definition — 1! = 1. may seem obvious, but very important, because lets us get definite answer for the factorial of a number. 17 18 For this example, let’s choose a nice round number. 5. 19 20 `5! = 120`. How do we know that? `5*4*3*2*1` 21 22 so `5! = 120 = 5*4*3*2*1` 23 24 but the mathematicians here know that: 25 - `5! = 5*4! = 5*4*3! = 5*4*3*2! = 5*4*3*2*1!. 1!=1` from definition, therefore 26 - `5! = 5*4*3*2*1 = 120` 27 28 29 ## Java implementation — recursion 30 31 Keep that in mind. Now, Java code which you can follow along with. Do any of you know ternary operator? No…I will write expanded. Otherwise, ternary operator. 32 33 ```cpp 34 public class Factorial { 35 public static void main(String[] args) { 36 System.out.println(fact(5)); 37 } 38 39 public static int fact(int n) { 40 41 // Done simply using ternary operator: 42 // return (n==1)? 1 : n*fact(n-1); 43 44 if (n==1) { 45 return 1; // If n is 1, return 1 46 } 47 48 else { 49 return n*fact(n-1); // Otherwise, return n times factorial of a number one less 50 } 51 } 52 } 53 ``` 54 55 In the else statement, there is *recursion*. The method fact is calling itself. If you don’t understand what that does yet, let me show it to you. 56 57 ## Code flow explanation 58 Indentation shows different levels of execution within the program. 59 60 Method main runs and asks the factorial method — what is fact5? 61 62 ``` 63 main: fact(5)? 64 65 fact: 66 fact5 - 5*fact4 - fact4? 67 fact4 - 4*fact3 - fact3? 68 fact3 - 3*fact2 - fact2? 69 fact2 - 2*fact1 - fact1? 70 fact1 - 1 (‘if’ part of statement runs) 71 fact2 - 2*1 - return 2 72 fact3 - 3*2 - return 6 73 fact4 - 4*6 - return 24 74 fact5 - 5*24 - return 120 75 76 main: fact(5) = 120 77 ``` 78 79 Basically, it’s just a huge stack of the method calling itself over and over again until it hits the ‘if’ part of the statement (until n is 1) and returns a specific value, and that’s passed back along the stack until you get a concrete result. That’s recursion. 80 81 ## Ruby implementation 82 83 ```ruby 84 def fact n 85 return n==1? 1 : n*fact(n-1) 86 end 87 88 puts fact(5) 89 ```