Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

h

a guest Feb 22nd, 2018 67 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. /*
  2. Recursion
  3. 02/20/18
  4.  */
  5. package javaapplication2;
  6.  
  7. import java.util.Scanner;
  8.  
  9. public class JavaApplication2 {
  10.  
  11.     /*
  12.     Returns factorial for given n
  13.     0! = 1
  14.     1! = 1
  15.     2! = 2
  16.     3! = 6
  17.      */
  18.     static int getFactIter(int n) {
  19.         int fact = 1;
  20.         for (int i = 2; i <= n; i++) {
  21.             fact *= i;
  22.         }
  23.         return fact;
  24.     }
  25.  
  26.     /*
  27.      Recursive method for above method
  28.      n! = (n-1)!*n
  29.      */
  30.     static int getFact(int n) {
  31.  
  32.         if (n == 0) {
  33.             System.out.println();
  34.             return 1;
  35.         }
  36.  
  37.         return getFact(n - 1) * n;
  38.     }
  39.  
  40.     /*    
  41.      Summation
  42.      1+2+3+4+...+n
  43.      */
  44.     static int getSum(int n) {
  45.  
  46.         if (n == 1) {
  47.             return 1;
  48.         }
  49.         return getSum(n - 1) + n;
  50.     }
  51.  
  52.     /*    
  53.      If given n = 12345
  54.      return 15
  55.      */
  56.     static int getDigitSum(int n) {
  57.         if (n == 0) {
  58.             return 0;
  59.         }
  60.         return getDigitSum(n / 10) + n % 10;
  61.     }
  62.  
  63.     // Goes through recursive method one less time than getDigitSum
  64.     static int getDigitSum1(int n) {
  65.         if (n < 10) {
  66.             return n;
  67.         }
  68.         return getDigitSum(n / 10) + n % 10;
  69.     }
  70.  
  71.     /*
  72.      Reverse string s
  73.       s = abcde
  74.       r = edcba
  75.      */
  76.     static String reverse(String s) {
  77.         if (s.length() == 1) {
  78.             return s;
  79.         }
  80.         return s.charAt(s.length() - 1) + reverse(s.substring(0, s.length() - 1));
  81.     }
  82.  
  83.     // Faster reverse
  84.     static String reverse1(String s) {
  85.         if (s.length() == 1) {
  86.             return s;
  87.         }
  88.         return s.charAt(s.length() - 1) + reverse(s.substring(1, s.length() - 1)) + s.charAt(0);
  89.     }
  90.  
  91.     /*
  92.      b^n
  93.      2^n = 2^(n-1)*2, 2^0 = 1
  94.      Same as inducion proofs in 195
  95.      */
  96.     // Count Var to see which is faster
  97.     static int cnt1 = 0;
  98.  
  99.     static int getPow(int b, int n) {
  100.         cnt1++;
  101.         if (n == 0) {
  102.             return 1;
  103.         }
  104.         return getPow(b, n - 1) * b;
  105.     }
  106.  
  107.     /*
  108.      2^10, 2^9, 2^8, ... 1
  109.    
  110.     Quicker way:
  111.     Even power:
  112.         2^16 = 2^8 * 2^8,
  113.         2^8  = 2^4 * 2^4,
  114.         2^4  = 2^2 * 2^2,
  115.         2^2  = 2   * 2
  116.    
  117.     Odd Power:
  118.         2^14 = 2^7 * 2^7
  119.         2^7  = 2^3 * 2^3 * 2
  120.      */
  121.     // Count Var to see which is faster
  122.     static int cnt2 = 0;
  123.  
  124.     static int getPowFaster(int b, int n) {
  125.         cnt2++;
  126.         if (n == 0) {
  127.             return 1;
  128.         }
  129.         int t = getPowFaster(b, n / 2);
  130.         if (n % 2 == 0) {
  131.             return t * t;
  132.         }
  133.         return t * t * b;
  134.     }
  135.  
  136.     /*
  137.      Fibonacci numbers
  138.      f(n) = f(n - 1) + f(n - 2)
  139.      f(1) = 1
  140.      f(2) = 1
  141.      */
  142.     static int getFibo(int n) {
  143.         if(n <= 2)
  144.             return 1;
  145.         return getFibo(n - 2) + getFibo(n - 1);
  146.     }
  147.    
  148.     // Tower of Hanoi
  149.     static void towerHanoi(int n, char p1, char p2, char p3) {
  150.         if(n > 0){
  151.             towerHanoi(n - 1, p1, p3, p2);
  152.             System.out.println(p1+" -> "+p3);
  153.             towerHanoi(n - 1, p2, p1, p3);    
  154.         }
  155.     }
  156.  
  157.     public static void main(String[] args) {
  158.  
  159. //        System.out.println(getPow(2, 20));
  160. //        System.out.println(getPowFaster(2, 20));
  161. //        System.out.println("GetPow: "+cnt1+" | GetPowFaster: "+cnt2);
  162. //        System.out.println(getFibo(8));
  163.           towerHanoi(10, 'A', 'B', 'C'); // 2^ n times
  164.  
  165.     }
  166. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top