import java.util.List;

class RekursiveMetoder{
    /**
    *Returnerer summen av alle tallene i int 2D array.
    *Dette gj?res rekursivt
    *@param array: int[][] tallene som skal summeres
    *@return summen av alle tallene i array
    */
    public static int leggSammen2DArray(int[][] array){
        return leggSammen2DArrayRek(0, array);
    }

    /**
     * Rekursiv hjelpemetode
     * @param teller: int, hvor langt vi har kommet
     * @param array: int[][], arrayet som skal summeres
     * @return summen
     */
    private static int leggSammen2DArrayRek(int teller, int[][] array) {
        if (teller == array.length) {
            return 0;
        }
        return leggSammenArray(0, array[teller]) + leggSammen2DArrayRek(teller+1, array);
    }

    private static int leggSammenArray(int teller, int[] array) {
        if (teller == array.length) {
            return 0;
        }
        return array[teller] + leggSammenArray(teller+1, array);
    }

    /**
    *Konkantinerer alle stringen i en liste i riktig rekkef?lge
    *@param ord: alle stringen som skal konkantineres
    *@return en string av alle ordene i lista i riktig rekkef?lge
    */
    public static String hentStringRiktigVei(List<String> ord){
        if (ord.isEmpty()) {
            return "";
        }
        return ord.remove(0) + hentStringRiktigVei(ord);
    }
    /**
    *konkantinerer alle stringen i en liste, i feil rekkef?lge
    *@param ord: alle stringen som skal konkantineres
    *@return en string av alle ordene i lista i feil rekkef?lge
    */
    public static String hentStringFeilVei(List<String> ord){
        if (ord.isEmpty()) {
            return "";
        }
        String s = ord.remove(0);
        return hentStringFeilVei(ord) + s;
    }

    /**
    *Leter nedover og til h?yere i arrayet for ? finne en tekst . Dette l?ses rekursivt 
    *@param ord:  arrayet som innholder alle strengene 
    *@param indeks1: bestemmer om man skal "g? opp eller ned" i arrayet
    *@param indeks2: bestemmer om man skal "g? til h?yere eller venstere" i arrayet
    *@return en tekst.
    */
    public static String finnTekst(String[][] ord, int indeks1, int indeks2){
        if(ord.length <= indeks1 || ord[0].length <= indeks2) return null;

        if(ord[indeks1][indeks2] == null) return null;
        
        String ned = finnTekst(ord, indeks1 + 1, indeks2);
        String hoyre = finnTekst(ord, indeks1, indeks2 + 1);

        if(ned != null) return ord[indeks1][indeks2] + " " + ned;

        if(hoyre != null) return ord[indeks1][indeks2] + " " +  hoyre;

        return ord[indeks1][indeks2];

    }
}