> For the complete documentation index, see [llms.txt](https://nissan-goldberg.gitbook.io/java101/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nissan-goldberg.gitbook.io/java101/lesson-7/recursion.md).

# Recursion

#### Exercise: Factorial Recursively

```java
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](https://qph.fs.quoracdn.net/main-qimg-ad0f90f6d7b09a9c36a192f21293b17e.webp)

or in one line

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

###

### Exercise - Reverse Recursively

```java
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

```java
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](https://i.ibb.co/hXnrRWz/permutation-Recursion.png)

####

#### 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
$$

```java
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

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

```
5
```

![Program to generate recursion tree for generic recursive program - Stack Overflow](https://i.stack.imgur.com/zmshy.png)

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

###

### Exercise: Reduce

![Reduec-java](https://i.ibb.co/7YJM5kF/Reduec-java.jpg)

```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

```java
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](http://www.hamilton.ie/mathschallenge/Sudoku2x2.jpg)

```java
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](https://www.geeksforgeeks.org/sudoku-backtracking-7/)

**code only**

```java
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
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nissan-goldberg.gitbook.io/java101/lesson-7/recursion.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.