JetBrains Academy: Recursion

Fix the method to print strings in the reverse order:

Given a recursive method which should print an input string in the reverse order.

Now the method prints the string in the same order. Fix the method.

After your fix, the method must be recursive.

import java.util.Scanner;

public class Main {

    /* Fixed method */
    public static void printReverseCharByChar(String s) {
        if (s.length() > 0) {
            int last = s.length() - 1;
            System.out.print(s.charAt(last));
            printReverseCharByChar(s.substring(0, last));
        }
    }

    /* Do not change code below */
    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        printReverseCharByChar(scanner.nextLine());
    }
}

N-th power:

It is possible to find a n-th power much quicker than by making n multiplications!

To do this you need to use the following recurrence relations:

aⁿ = (a²)^n/2 for even n,

aⁿ = a * a^n-1 for odd n.

Implement the algorithm of quick exponentiating using a recursion method.

import java.util.Scanner;

public class Main {

    public static double pow(double a, long n) {
        // write your code here
        if (n == 0) {
            return 1;
        } else if (n % 2 == 0) {
            return pow(a * a, n / 2);
        } else {
            return a * pow(a, n - 1);
        }
    }

    /* Do not change code below */
    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final double a = Double.parseDouble(scanner.nextLine());
        final int n = Integer.parseInt(scanner.nextLine());
        System.out.println(pow(a, n));
    }
}

Alternating Fibonacci numbers:

Given the small integer n (0 <= n <= 40) you need to find the n-th number of the alternating Fibonacci sequence.

The sequence starts with 0, 1, -1, 2, -3, 5, -8, 13, -21, ...

So, fib(0) = 0, fib(1) = 1 => fib(2) = -1.

Think of the recurrence relation and implement the method named fib in a recursive way. It's not efficient in the general but works well for small n.

import java.util.Scanner;

public class Main {

    public static long fib(long n) {
        long fibbonacciNumber = 0;
        if (n % 2 == 0) {
            fibbonacciNumber = -fibHelper(n);
        } else {
            fibbonacciNumber = fibHelper(n);
        }
        return fibbonacciNumber;
    }
    
    private static long fibHelper(long n) {
        if (n <= 1) {
            return n;
        } else {
            return fibHelper(n - 1) + fibHelper(n - 2);
        }
    }

    /* Do not change code below */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(fib(n));
    }
}

K-combination:

Let's introduce the term k-combination. It is a subset of k distinct elements of this set.

Two combinations are called different if one of the combinations contains an element, which is not present in the other combination.

The number of k-combinations of a set of n elements is the number of different such combinations. Let’s write this number as C(n, k).

It is easy to understand that C(n, 0) = 1, as you can select 0 elements from the set of n elements by the only way: namely, by not choosing anything.
Also, it is easy to understand that if k > n, then C(n, k) = 0, as it is impossible, for example, to choose five elements from the three given ones.
The following recurrent formula is used to calculate C(n, k) in the other cases: C(n, k) = C(n - 1, k) + C(n - 1, k - 1).

Instruction:
Implement a method, which calculates C(n, k) for the specified n and k.

It should use the recurrent formula to calculate C(n, k).

Example:
Let n = 3, i.e. there are three elements (1, 2, 3). Let k = 2.
All the different 2-combination of 3 elements: (1, 2), (1, 3), (2, 3).
There are three different combinations, thus C(3, 2) = 3.

import java.util.Scanner;

public class Main {

    public static int comb(int n, int k) {
        // write your code here
        if (k == 0) {
            return 1;
        } else if (k > n) {
            return 0;
        } else {
            return comb(n - 1, k) + comb(n - 1, k - 1);
        }
    }

    /* Do not change code below */
    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int n = scanner.nextInt();
        final int k = scanner.nextInt();
        System.out.println(comb(n, k));
    }
}

Number of decompositions:

Read the integer N (1 ≤ N ≤ 40) from the standard input and list all the decompositions of NN into a sum of positive integers. The addends should go in non-ascending order within each decomposition.

Output all decompositions in the lexicographical order.

Please, use a recursive method to write your solution.

import java.util.Scanner;
 
class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int toDecompose = scanner.nextInt();
 
        decompose(toDecompose, toDecompose, "");
    }
 
    private static void decompose(int toDecompose, int max, String out) {
        if (toDecompose == 0) {
            System.out.println(out);
        } else if (toDecompose > 0) {
            for (int i = 1; i <= max; i++) {
                decompose(toDecompose - i, i, out + i + " ");
            }
        }
    }
}

JetBrains Academy: Recursion - Kamil-Jankowski/Learning-JAVA GitHub Wiki

JetBrains Academy: Recursion

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️