using System;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        factorial();

        Console.WriteLine();

        fib();

        Console.WriteLine();

        tripleStep();

    }

    static void factorial(){

        int n = 5;

        int result = factorial(5);

        Console.Write("factorial of " + n + " is " + result);

    }

    static int factorial(int n){

        if(n == 1) return 1;

        return n * factorial(n-1);

    }

    static void fib(){

        int n = 5;

        int result = fib(5);

        Console.Write("fibonacci of " + n + " is " + result);

    }

    static int fib(int n){

        if(n == 0) return 0;

        if(n == 1) return 1;

        return fib(n-1) + fib(n-2);

    }

    static void tripleStep(){

        int n = 5;

        int result = tripleStep(5);

        Console.Write("tripleStep of " + n + " is " + result);

        Console.WriteLine("\n\tRuntime is 3^n." + 

                          "\n\treturn tripleStep(n-3) + tripleStep(n-2) + tripleStep(n-1);" + 

                          "\n\tThis is branches times depth recursion");

    }

    static int tripleStep(int n){

        if(n < 0) return 0;

        if(n == 0) return 1;

        return tripleStep(n-3) + tripleStep(n-2) + tripleStep(n-1);

    }

    static int magicIndex(int[] arr, int low, int high){

        int mid = (low + high)/2;

        if(arr[mid] == mid){

            return mid; 

        }

        int left = Math.Min(arr[mid], mid-1);

        int leftResult = magicIndex(arr, left, high);   

        if(leftResult > -1) return leftResult;

        int right = Math.Max(arr[mid], mid +1);

        return magicIndex(arr, right, high);    

    }

}