Recursion

Exercise: Factorial Recursively

public class Main {
    public static int factorial(int n){
        if (n==0 || n==1)
            return 1;
        //also check
        if (n<0)
            return -1;

        return n*factorial(n-1);
    }

    public static void main(String[] args) {
        int n = 5;
        int res = factorial(n);
        System.out.println(res);
    }
}

120

What is the writing program for a factorial using recursion with the main function used only? - Quora

or in one line

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

Exercise - Reverse Recursively

public class Main {
    public static String reverse_rec(String str){
        if (str.equals(""))
            return "";

        // String substring(from = 0, to = Integer.MAX_VALUE)
        //from 1 to the end
        return reverse_rec(str.substring(1)) + str.charAt(0);
        //iteration 1: reverse_rec(ello) + h
        //iteration 2: reverse_rec(llo) + eh
        //..
    }

    public static void main(String[] args) {
        String str = "hello";
        System.out.println(reverse_rec(str));
    }
}

olleh

Exercise: Print all permutations Recursively

public class Main {

    public static void main(String[] args) {
        permutationWrapper("ABC");
    }

    //wrapper function
    public static void permutationWrapper(String str1) {
        permutation(str1, ""); //recursive function
    }


    public static void permutation(String str1, String NewStringToPrint) {
        //===base case===
        if (NewStringToPrint.length() == str1.length()) {
            System.out.println(NewStringToPrint);
            return;
        }

        for (int i = 0; i < str1.length(); i++)
            permutation(str1, NewStringToPrint + str1.charAt(i));
    }
}

AAA
AAB
AAC
...
CCB
CCC

permutation-Recursion

Exercise: Fibonacci

$$F_{n}=F_{n-1}+F_{n-2}$$

and

$$F_{0}=0,\quad F_{1}=1$$

sequence:

$$1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;\ldots$$

public class Main {
    public static int fib_rec(int n){
        if (n==0)
            return 0;

        if (n==1)
            return 1;

        return fib_rec(n-1)+fib_rec(n-2);
    }

    public static void main(String[] args) {
        int n = 8;
        System.out.println(fib_rec(n));
    }
}

21

another IO

int n = 5;
System.out.println(fib_rec(n));

5

Program to generate recursion tree for generic recursive program - Stack Overflow

$$1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;\ldots$$

Exercise: Reduce

Reduec-java

public class Main {

    //return abc
    public static String reduce(String str){

        if (str.length()==1 || str.length()==0 )
            return str;

        char next = str.charAt(1); //next char
        char current = str.charAt(0); //next char

        //if next char is the same
        if (current == next)
            return reduce(str.substring(1, str.length()));
        else //if next char is the not tge same
            return current + reduce(str.substring(1, str.length()));
    }

    public static void main(String[] args) {
        System.out.println(reduce("aaabbbbcddde"));
        System.out.println(reduce("abbbbcdddeee"));
    }
}

abcde

Exercise: All subarrays

public class Main {
    // Recursive function to print all possible subarrays
// for given array
    public static void printSubArrays(int []arr, int start, int end) {
        // Stop if we have reached the end of the array
        if (end == arr.length)
            return;

        // Increment the end point and start from 0
        else if (start > end)
            printSubArrays(arr, 0, end + 1);

        // Print the subarray and increment the starting point
        else {
            System.out.print("(");
            for (int i = start; i < end; i++){
                System.out.print(arr[i]+", ");
            }

            System.out.println(arr[end]+")");
            printSubArrays(arr, start + 1, end);
        }

        return;
    }

    public static void main(String args[]) {
        int []arr = {1, 2, 3};

        System.out.print("Array : ");
        for (int val:arr)
            System.out.print(val + " ");
        System.out.println("\n=== subarrays ===");

        printSubArrays(arr, 0, 0);

    }
}

Array : 1 2 3 
=== subarrays ===
(1)
(1, 2)
(2)
(1, 2, 3)
(2, 3)
(3)

Exercise: Sudoku 2x2

Hamilton Institute Schools Maths Challenge

package com.company;

// Java program for above approach
public class Main {

    // N is the size of the 2D matrix N*N
    static int N = 4;

    /* Takes a partially filled-in grid and attempts
    to assign values to all unassigned locations in
    such a way to meet the requirements for
    Sudoku solution (non-duplication across rows,
    columns, and boxes) */
    static boolean solveSuduko(int grid[][], int row,
                               int col) {

        /*if we have reached the 3th
        row and 4th column (0
        indexed matrix) ,
        we are returning true to avoid further
        backtracking     */
        if (row == N - 1 && col == N)
            return true;

        // Check if column value becomes 4 ,
        // we move to next row
        // and column start from 0
        if (col == N) {
            row++;
            col = 0;
        }

        // Check if the current position
        // of the grid already
        // contains value >0, we iterate
        // for next column
        if (grid[row][col] != 0)
            return solveSuduko(grid, row, col + 1);

        for (int num = 1; num <= 4; num++) {

            // Check if it is safe to place
            // the num (1-4) in the
            // given row ,col ->we move to next column
            if (isSafe(grid, row, col, num)) {

                /* assigning the num in the current
                (row,col) position of the grid and
                assuming our assined num in the position
                is correct */
                grid[row][col] = num;

                // Checking for next
                // possibility with next column
                if (solveSuduko(grid, row, col + 1))
                    return true;
            }
            /* removing the assigned num , since our
            assumption was wrong , and we go for next
            assumption with diff num value */
            grid[row][col] = 0;
        }
        //got stuck on number
        // ex 1 3 2, incorrect, since 1 3 2 4
        //                            . . . 4
        //but rather 1 3 4
        return false;
    }

    /* A utility function to print grid */
    static void print(int[][] grid) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                System.out.print(grid[i][j] + " ");
            System.out.println();
        }
    }

    // Check whether it will be legal
    // to assign num to the
    // given row, col
    static boolean isSafe(int[][] grid, int row, int col,
                          int num) {

        // Check if we find the same num
        // in the similar row , we
        // return false
        for (int x = 0; x <= 3; x++)
            if (grid[row][x] == num)
                return false;

        // Check if we find the same num
        // in the similar column ,
        // we return false
        for (int x = 0; x <= 3; x++)
            if (grid[x][col] == num)
                return false;

        // Check if we find the same num
        // in the particular 2*2
        // matrix, we return false
        int startRow = row - row % 2, startCol
                = col - col % 2;
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                if (grid[i + startRow][j + startCol] == num)
                    return false;

        return true;
    }

    // Driver Code
    public static void main(String[] args) {
        int grid[][] = { { 1, 0, 0, 0},
                         { 0, 2, 0, 0},
                         { 0, 0, 3, 0},
                         { 0, 0, 0, 4} };

        if (solveSuduko(grid, 0, 0))
            print(grid);
        else
            System.out.println("No Solution exists");
    }
    // This is code is contributed by Pradeep Mondal P
}

1 3 4 2 
4 2 1 3 
2 4 3 1 
3 1 2 4

Source

code only

package com.company;

public class Main {

    static int N = 4;

    static boolean solveSuduko(int grid[][], int row,
                               int col) {

        if (row == N - 1 && col == N)
            return true;

        if (col == N) {
            row++;
            col = 0;
        }

        if (grid[row][col] != 0)
            return solveSuduko(grid, row, col + 1);

        for (int num = 1; num <= 4; num++) {
            if (isSafe(grid, row, col, num)) {
                grid[row][col] = num;

                if (solveSuduko(grid, row, col + 1))
                    return true;
            }
            grid[row][col] = 0;
        }
        return false; //got stuck on number
    }

    /* A utility function to print grid */
    static void print(int[][] grid)
    {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                System.out.print(grid[i][j] + " ");
            System.out.println();
        }
    }

    // Check whether it will be legal to assign num to the given row, col
    static boolean isSafe(int[][] grid, int row, int col,
                          int num) {

        for (int x = 0; x <= 3; x++)
            if (grid[row][x] == num)
                return false;

        for (int x = 0; x <= 3; x++)
            if (grid[x][col] == num)
                return false;

        int startRow = row - row % 2, startCol
                = col - col % 2;
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                if (grid[i + startRow][j + startCol] == num)
                    return false;

        return true;
    }

    public static void main(String[] args) {
        int grid[][] = { { 1, 0, 0, 0},
                         { 0, 2, 0, 0},
                         { 0, 0, 3, 0},
                         { 0, 0, 0, 4} };

        if (solveSuduko(grid, 0, 0))
            print(grid);
        else
            System.out.println("No Solution exists");
    }
}

1 3 4 2 
4 2 1 3 
2 4 3 1 
3 1 2 4