// this is how to find fibonachi number with recursion 

public class Main {
    public static void main(String[] args) {
        System.out.println(fibo(6));

    }
    static int fibo(int n){

        //base condition
        if(n<2){        // if searched number is 0 or 1 = retunn n
            return n;
        }
        return fibo(n-1)+fibo(n-2);
    }
}

////////////////////////////////////////////////////////
// this is a binary search with a recursion
public class Main {
    public static void main(String[] args) {
        int [] arr={1,2,3,4,5,76,78,657};
        int target=4;
        System.out.println(search(arr,target,0, arr.length-1));

    }
    static int search(int[] arr,int target,int s,int e){

        if(s>e){
            return -1;
        }
        int m=s+(e-s)/2;
        if(arr[m]==target){
            return m;
        }
        if(target<arr[m]){
            return search(arr,target,s,m-1);  // <-- make sure to return a value
        }
        return search(arr, target, m+1, e);
    }
}

////////////////////////////

// this is a simple recurion program taht calls sayHi method n times

public class Main {
    public static void main(String[] args) {
        sayHi(5);

    }
    public static void sayHi(int count) {
        System.out.println("hello");
        
       if(count<=1){
           return;  // this exits recursion sort of like break 
       }
       sayHi(count-1); // each time recursion happens count is smaller to at end recurion finishes
        }

    }