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;
    }

}



public static int power3(int n, int e) {
    if (e == 0) return 1;
    int number = n;
    int secondNumber = power3(n, e - 1);
    return number * secondNumber;
}


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);
    }
}


public static int countZeros(int n) {
    if (n == 0) {
        return 0;
    }
    if (n % 10 == 0) {
        return 1 + countZeros(n / 10);  // Add 1 if current digit is zero
    } else {
        return countZeros(n / 10);  // Otherwise, continue without adding
    }
}



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);
    }

}


17.2. Find element of an array like this: {5, 6, 7, 8, 9, 1, 2, 3}


public static int search(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 (arr[start] <= arr[mid]) {
        if (target >= arr[start] && target <= arr[mid]) {
            return search(arr, target, start, mid - 1);
        } else {
            return search(arr, target, mid + 1, end);
        }
    }

    if (target >= arr[mid] && target <= arr[end]) {
        return search(arr, target, mid + 1, end);
    }
    return search(arr, target, start, mid - 1);
}



18. Sum of Triangle from array

https://www.geeksforgeeks.org/sum-triangle-from-array/


public static void sumTriangle(int[] arr) {
    if (arr.length < 1) {
        return;
    }
    int[] nextArr = new int[arr.length - 1];
    for (int i = 0; i < arr.length - 1; i++) {
        nextArr[i] = arr[i] + arr[i + 1];
    }
    sumTriangle(nextArr);
    System.out.println(Arrays.toString(arr));
}



19. Bubble sort:


public static int[] bubble3(int[] arr, int swaps, int size) {
    if (swaps == 0 || size == 1) return arr;
    swaps = 0;
    for (int i = 0; i < size - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            int temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
            swaps++;
        }
    }
    return bubble3(arr, swaps, size - 1);
}



public static void bubble(int[] arr, int c, int r) {
    if (r == 0) return;
    if (c < r) {
        if (arr[c] > arr[r]) {
            int temp = arr[c];
            arr[c] = arr[r];
            arr[r] = temp;
        }
        bubble(arr, c + 1, r);
    } else {
        bubble(arr, 0, r - 1);
    }
}


20. Selection sort:

package com.example;

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int[] arr = {5, 6, 7, 8, 9, 1, 2, 3};
        selection2(arr, arr.length, 0, 0);
        System.out.println(Arrays.toString(arr));
    }

    public static void selection(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }

    public static void selection2(int[] arr, int r, int c, int max) {
        if (r == 0) return;
        if (c < r) {
            if (arr[c] > arr[max]) {
                selection2(arr, r, c + 1, c);
            } else {
                selection2(arr, r, c + 1, max);
            }
        } else {
            int temp = arr[max];
            arr[max] = arr[r - 1];
            arr[r - 1] = temp;
            selection2(arr, r - 1, 0, 0);
        }
    }

}


21. Product of an array:

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


22. Recursive range:

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


23. Reverse word:


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


24. Capitalize first words:

public static String capitalizeWord2(String str) {
    if (str.length() == 0) return "";
    char first = str.charAt(str.length() - 1);
    if (str.length() == 1) {
        first = (char) (first - 32);
        return Character.toString(first);
    }
    if (str.substring(str.length() - 2, str.length() - 1).equals(" ")) {
        first = (char) (first - 32);
    }
    return capitalizeWord2(str.substring(0, str.length() - 1)) + first;
}



































Комментарии

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

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

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_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...
Далее...

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...
Далее...