Recursion - HackMD

# Recursion --- # Why recursion? Recursion can do everything a _loop_ can do and more. But not vice versa. --- # Definition **Recursion** is a method of solving problems where you solve smaller portions of the problem until you solve the larger problem. ---- ## A simpler definition A function that calls itself ```java void fn() { System.out.println("hi"); fn(); } ``` What would the above code do? ---- **How do you make it stop?** ```java= void fn(int i) { if (i == 0) return; System.out.println("hi"); fn(i - 1); } ```  By introducing the _base condition_  Compare that to a for-loop ```java= for(int i=0; i<10; i++) System.out.println("hi"); ```  --- **So again, why recursion over a loop?** If both are our options, we tend to use the loop for its simplicity and generally faster speed. However, there are questions that loops cannot handle. --- # Learning strategy 1. Write simple recursions 2. Trace recursive programs 3. Write more complicated recursions --- ## Which type are _you?_ Given N homeworks assignments, 1. Finish all today! 💪 <span>==for==</span> 2. Finish 1 and do the rest tomorrow 😉 <span>==recursion==</span> 3. Do 'em tomorrow 😉😜😜 ---- ## recursion mentality 1. Try to contribute as little as you can (but not zero) 2. Trust your friends --- # Exercise ``` Q. Print 1, 2, 3, ..., N ``` - Person 1 - prints 1 - asks friend to print 2 ~ 10  - Person 2 - prints 2 - asks friends to print 3 ~ 10  ---- ```java= void print(int n) { // base condition (aka lucky guy) if (n == 0) return; // my contribution System.out.println(n); // foisting print(n-1); } ``` --- ``` Q. Calculate the sum of numbers 1+2+3+4...+N ``` - P1 - asks friends for 2 + 3 + 4 + ... + N - add 1 to **that**.  - P2 - asks friends for 3 + 4 + ... N - adds 2 to **that**.  ```java int sum(int start, int n) { if (start == n) return n; return start + sum(start+1, n); } ```  --- > To understand recursion, one must first understand recursion