DSA: Recursion

1. Factorial:


package main.lesson5;

public class Main {
    public static void main(String[] args) {
        System.out.println(factorial(5));
        System.out.println(factorial2(5));
    }

    public static int factorial(int n) {
        if (n == 0) return 1;
        return n * factorial(n - 1);
    }

    public static int factorial2(int n) {
        int currentValue = n;
        if (currentValue == 0) {
            return 1;
        }
        int previousValue = currentValue - 1;
        int recursiveResult = factorial(previousValue);
        int result = currentValue * recursiveResult;
        return result;
    }

} 



2. Fibonacci:


package main.lesson5;

public class Main {
    public static void main(String[] args) {
        System.out.println(fibonacci(6));
    }

    public static int fibonacci(int n) {
        if(n == 0 || n == 1) return n;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static int fibonacci2(int n) {
        if (n == 0 || n == 1) return n;
        int first = fibonacci(n - 1);
        int second = fibonacci(n - 2);
        return first + second;
    }
}



3. Sum of digits of a number:


package main.lesson5;

public class Main {
    public static void main(String[] args) {
        System.out.println(sumOfDigits(123));
    }

    public static int sumOfDigits(int n) {
        if (n == 0) return 0;
        return n % 10 + sumOfDigits(n / 10);
    }
}



4. Power:


package main.lesson5;

public class Main {
    public static void main(String[] args) {
        System.out.println(power(5, 3));
        System.out.println(power2(5, 3));
    }

    public static int power(int number, int exponent) {
        if (exponent == 0) return 1;
        return number * power(number, exponent - 1);
    }

    public static int power2(int number, int exponent) {
        if (exponent == 0) return 1;
        int result = power2(number, exponent - 1);
        return result * number;
    }

}




5. Product of an Array:

package main.lesson5;

public class Main {
    public static void main(String[] args) {
        int[] arr = {3, 5, 9};
        System.out.println(productOfArray(arr, arr.length));
        System.out.println(productOfArray2(arr, arr.length));
    }

    public static int productOfArray(int arr[], int n) {
        if (n == 1) return arr[0];
        return arr[n - 1] * productOfArray(arr, n - 1);
    }

    public static int productOfArray2(int arr[], int n) {
        if (n == 1) return arr[0];
        int first = arr[n - 1];
        int productOfRest = productOfArray2(arr, n - 1);
        first *= productOfRest;
        return first;
    }
}


6. RecursiveRange:


package main.lesson5;

public class Main {
    public static void main(String[] args) {
        System.out.println(recursiveRange(6));
        System.out.println(recursiveRange2(6));
    }

    public static int recursiveRange(int num) {
        if (num == 1) return 1;
        return num + recursiveRange(num - 1);
    }

    public static int recursiveRange2(int num) {
        if (num == 1) return 1;
        int result = num;
        int remainder = recursiveRange2(num - 1);
        return result + remainder;
    }
}



7. Reverse:


package main.lesson5;

public class Main {
    public static void main(String[] args) {
        System.out.println(reverse("java"));
        System.out.println(reverse2("java"));
    }

    public static String reverse(String str) {
        if (str.length() == 1) return str;
        return reverse(str.substring(1)) + str.charAt(0);
    }

    public static String reverse2(String str) {
        if(str.length() == 1) return str;
        String s = reverse(str.substring(1));
        return s + str.charAt(0);
    }
}



8. IsPalindrome:


package main.lesson5;

public class Main {
    public static void main(String[] args) {
        System.out.println(isPalindrome("awesome"));
        System.out.println(isPalindrome("foobar"));
        System.out.println(isPalindrome("tacocat"));
        System.out.println(isPalindrome("amanaplanacanalpanama"));
        System.out.println(isPalindrome("amanaplanacanalpandemonium"));
    }

    public static boolean isPalindrome(String s) {
        if(s.length() == 0 || s.length() == 1) return true;
        if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
        return isPalindrome(s.substring(1, s.length() - 1));
    }
}



9. First uppercase:


package main.lesson5;

public class Main {
    public static void main(String[] args) {
        System.out.println(first("jaVa"));
        System.out.println(first("java"));
    }

    public static char first(String str) {
        if (str.charAt(0) > 64 && str.charAt(0) < 91) return str.charAt(0);
        if(str.length() == 1) return str.charAt(0);
        return first(str.substring(1));
    }
}



10. Capitalize Word:


package main.lesson5;

public class Main {
    public static void main(String[] args) {
        System.out.println(capitalizeWord("parvin"));
    }

    public static String capitalizeWord(String str) {
        if (str.length() == 0) return "";
        char first = str.charAt(0);
        if (first > 96 && first < 123) {
            first = (char) (first - 32);
        }
        return first + capitalizeWord(str.substring(1));
    }
}



11. GCD:


package main.lesson5;

public class Main {
    public static void main(String[] args) {
        System.out.println(gcd(8, 12));
        System.out.println(gcd(12, 8));
        System.out.println(gcd2(12, 8));
    }

    public static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    public static int gcd2(int a, int b) {
        if (b == 0) return a;
        int remainder = a % b;
        return gcd2(b, remainder);
    }

}


12. Decimal to Binary:


package main.lesson5;

public class Main {
    public static void main(String[] args) {
        System.out.println(decimalToBinary(14));
        System.out.println(decimalToBinary2(14));
    }

    public static int decimalToBinary(int decimal) {
        if (decimal == 1) return 1;
        return decimalToBinary(decimal / 2) * 10 + decimal % 2;
    }

    public static int decimalToBinary2(int decimal) {
        if (decimal == 1) return 1;
        int quotient = decimalToBinary2(decimal / 2);
        int remainder = decimal % 2;
        return quotient * 10 + remainder;
    }

}



13. Binary search:


package main.lesson5;

public class Main {
    public static void main(String[] args) {
        int[] arr = {5, 9, 10, 17, 33, 39, 43, 70};
        System.out.println(binarySearch(arr, 5, 0, arr.length - 1));
        System.out.println(binarySearch(arr, 9, 0, arr.length - 1));
        System.out.println(binarySearch(arr, 10, 0, arr.length - 1));
        System.out.println(binarySearch(arr, 17, 0, arr.length - 1));
        System.out.println(binarySearch(arr, 33, 0, arr.length - 1));
        System.out.println(binarySearch(arr, 39, 0, arr.length - 1));
        System.out.println(binarySearch(arr, 43, 0, arr.length - 1));
        System.out.println(binarySearch(arr, 70, 0, arr.length - 1));
    }

    public static int binarySearch(int[] arr, int target, int start, int end) {
        if (start > end) return -1;
        int mid = start + (end - start) / 2;
        if (arr[mid] == target) return mid;
        if (target > arr[mid]) {
            return binarySearch(arr, target, mid + 1, end);
        } else {
            return binarySearch(arr, target, start, mid - 1);
        }
    }
}


14. Reverse Number:


package main.lesson8;

public class Main {
    public static void main(String[] args) {
        System.out.println(reverseNumber(123));
    }

    public static int reverseNumber(int number) {
        if (number == 0) return 0;
        int digit = number % 10;
        int x = (int) Math.log10(number);
        return (int) (digit * Math.pow(10, x) + reverseNumber(number / 10));
    }

}


15. Count of zeros in a number:


package main.lesson8;

public class Main {
    public static void main(String[] args) {
        System.out.println(countOfZeros(203101, 0));
        System.out.println(countOfZeros(203101));
    }

    public static int countOfZeros(int number, int count) {
        if (number == 0) return count;
        if (number % 10 == 0) count++;
        return countOfZeros(number / 10, count);
    }

    public static int countOfZeros(int number) {
        if (number == 0) return 1;
        if (number < 10) return 0;
        return number % 10 == 0 ? 1 + countOfZeros(number / 10) : countOfZeros(number / 10);
    }
}


16. Is array sorted or not:


package main.lesson8;

public class Main {
    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4, 5};
        int[] arr2 = {1, 2, 3, 5, 4};
        int[] arr3 = {1, 3, 2, 4, 5};
        System.out.println(isArraySorted(arr1, 0));
        System.out.println(isArraySorted(arr2, 0));
        System.out.println(isArraySorted(arr3, 0));
    }

    public static boolean isArraySorted(int[] arr, int index) {
        if (index == arr.length - 1) return true;
//        return arr[index] < arr[index + 1] && isArraySorted(arr, index + 1);
        return arr[index] > arr[index + 1] ? false : isArraySorted(arr, index + 1);
    }

}


17. Find element index in an array:


package main.lesson8;

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 5, 18, 2, 0, 7};
        System.out.println(findElement(arr, 5, 0));
    }

    public static int findElement(int[] arr, int target, int index) {
        if(index == arr.length) return -1;
//        if(arr[index] == target) return index;
//        return findElement(arr, target, index+1);
        return arr[index] == target ? index : findElement(arr, target, index+1);
    }

}










Комментарии

Отправить комментарий

Популярные сообщения из этого блога

Lesson1: JDK, JVM, JRE

Изображение
1. Compiler - takes the entire programming code written in high language and translates the whole of it into machine code at once. After this process the an executable file will be ready to run. The translation takes some times to be done, but after that execution is so fast. 2. Interpreter - takes each single instructions of the code translates it and then executes it on its own. The translation step is before the program runs is fast, but execution is slow. JDK = JRE + development tools JRE = JVM + library class JDK -> Java Development Kit. A kit which provides the environment to develop and execute (run) Java program. JRE -> Java Runtime Environment. Provides environment to only run. JVM -> Java Virtual Machine f * Compiled: Fortran, C, C++, Pascal, Haskell, Rust, Go * Interpreted: JavaScript, PHP, Python, Ruby Java both compiled and interpreted language. Terminalda : javac Main.java yazdiqda, source fayli(.java) bytecode(.class) faylina cevirir. Terminalda: java Main (bu z
Далее...

SE_21_Lesson_11: Inheritance, Polymorphism

->  instanceof anlayishi, misallarla izahi   package org.example.lesson_13 ; public class Ulubaba { public String ad ; public String soyad ; public Integer yash ; public void odunDogramaq () { System . out .println( "Ulubaba 50 kq odunu 1 saata dograyir" ) ; } } package org.example.lesson_13 ; public class Baba extends Ulubaba { public String hobbi ; public void otBicmek () { System . out .println( "Baba 1 hektar otu 1 gune bicir" ) ; } } package org.example.lesson_13 ; public class Main { public static void main ( String [] args ) { Baba baba = new Baba() ; System . out .println( baba instanceof Ulubaba ) ; System . out .println( baba instanceof Object ) ; } } -> Upcasting package org.example.lesson_13 ; public class Main { public static void main ( String [] args ) { Ulubaba u = new Baba() ; } } -> Downcasting Problemsiz situasiya: package org.example.lesson_13
Далее...

SE_21_Lesson_9: Initialization Blocks, Wrapper types, String class

Изображение
-> static block: package org.example.test3 ; public class Blocks { static { System . out .println( "In static block" ) ; } public static void method () { System . out .println( "In static method" ) ; } } package org.example.test3 ; public class Main { public static void main ( String [] args ) { Blocks . method () ; } } -> Class.forName() metodunu ishe salmaq: package org.example.test3 ; public class Blocks { static { System . out .println( "In static block" ) ; } } package org.example.test3 ; public class Main { public static void main ( String [] args ) throws Exception { Class . forName ( "org.example.test3.Blocks" ) ; } } -> non-static (instance) block: package org.example.test3 ; public class Blocks { static { System . out .println( "in static block" ) ; } { System . out .println( "in non static (instance) block
Далее...