---
description: In this lab, we will talk about a new idea that will help us with a lot of problems, the concept of recursion is pretty simple, but applying it without understanding it is pretty hard!
---
<h1 style='border: none'><center>Programming I Lab 10</center></h1>
<h2 style='border: none'><center>Recursion</center></h2>
<h5><center>The Islamic University of Gaza<br>Engineering Faculty<br>Department of Computer Engineering</center></h5>
<h6>Author: Mohammed Nafiz ALMadhoun<span style="float:right">2021/12/03</span></h6>

---

<p style='text-align:justify'>
In this lab, we will talk about a new idea that will help us with a lot of problems, the concept of recursion is pretty simple, but applying it without understanding it is pretty hard!
</p>

## Lab Objectives
- Understand the concept of recursion.
- Be able to write recursive methods.

## Recursion

The idea of recursion is pretty simple, imagine you have a method and inside this method, you call the same method.

So you will have a method that calls itself, this will lead to making the code easier to understand and write in some complex problems that require itself!

### Fibonacci Number Example

The Fibonacci sequence is a sequence starts like this:
<center>

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...$
</center>

Each number in the sequence is just the sum of the previous two numbers, and the first and second number is our base, so they are just `0` and `1`, to write this in equations we can write:

$F_0 = 0$
$F_1 = 1$
$F_n = F_{n-2} + F_{n-1}$

#### Thinking about the code

The idea here is that you will select the base cases (Which will prevent the method from calling itself forever), then you will write the regular case.

public static int fib (int index) {
    if (index == 0)
        return 0;
    if (index == 1)
        return 1;
    
    return fib(index - 2) + fib(index - 1);
}

Notice that if the index is `0` or `1`, it will return a certain value, but if it's not `0` or `1`, it will return the summation of the two previous elements, which in the end will lead to getting the base values.

#### Calling Example

If we want to get the `fib(5)`, this will lead to calling the method `fib` multiple times like this:

digraph {
    node [shape=rect]
    
    fib_5 [label="fib(5)"]
    fib_3_0 [label="fib(3)"]
    fib_3_1 [label="fib(3)"]
    fib_2_0 [label="fib(2)"]
    fib_2_1 [label="fib(2)"]
    fib_2_2 [label="fib(2)"]
    fib_1_0 [label="fib(1)"]
    fib_1_1 [label="fib(1)"]
    fib_1_2 [label="fib(1)"]
    fib_1_3 [label="fib(1)"]
    fib_1_4 [label="fib(1)"]
    fib_0_0 [label="fib(0)"]
    fib_0_1 [label="fib(0)"]
    fib_0_2 [label="fib(0)"]
    fib_5 -> "fib(4)"
    fib_5 -> fib_3_0
    "fib(4)" -> fib_3_1
    "fib(4)" -> fib_2_2
    fib_2_2 -> fib_1_4
    fib_2_2 -> fib_0_2
    fib_3_0 -> fib_2_0
    fib_3_0 -> fib_1_0
    fib_2_0 -> fib_1_1
    fib_2_0 -> fib_0_0
    fib_3_1 -> fib_2_1
    fib_3_1 -> fib_1_2
    fib_2_1 -> fib_1_3
    fib_2_1 -> fib_0_1
}

<div style="page-break-after: always;"></div>

## Lab Tasks

### Task 1: Print the tree of Folders!

In this task, you will use `File` class, which will allow you to get all the files and folders in a certain folder using `listFiles` method, and you can check if this is a file or folder using the methods `isFile`, or `isDirectory`, for example:

public static void main(String[] args){
    File dir = new File("D:\\TA\\Programming");
    File[] list = dir.listFiles();
    for(File child : list){

        System.out.print(child.getName());
        if (child.isFile()) 
            System.out.println (" - File");
        else
            System.out.println (" - Folder");
    }
}

This code will print all the files and folders names in `D:\TA\Programming\` folder:
<center>

Files and Folders in the Folder
</center>

<center>

Code Output
</center>

Now, your task is to create a program that prints the tree of files in a certain folder, this will run recursivly because we don't know the depth of our tree.

<center>

</center>

###### tags: `Programming` `Java` `IUG`

<center>End Of Lab 10</center>