среда, 1 августа 2012 г.

module: recursion


Материал
Рекурсия
    - [Шилдт. Руководство] - стр 174-176
Сортировка слиянием
Быстрая сортировка

Подтемы

     Рекурсия, как и итерация(цикл), это программная конструкция, позволяющая вызвать другую программную конструкцию многократно. Она также создает локальные переменные на каждое обращение к внутренней конструкции. Есть ряд отличий:
- в цикл мы входим один раз, а в фрейм метода в стеке вызовов два раза при рекурсии без ветвлений(на входе, на выходе) и более двух раз при рекурсии с ветвлением.
    Рекурсия бывает прямая и косвенная. При прямой функция вызывает саму себя непосредственно, при косвенной функция вызывает саму себя опосредованно, через вызов другой функции/функций.
    Про внутреннюю структуру данных виртуальной машины Фрейм Метода вы можете прочитать в спецификации виртуальной машины.


ИДИОМА: Рекурсия без ветвлений


Рекурсия без ветвлений, "print на входе":

public class RecursionPrintIn {



    public static void main(String[] args) {



        f(1);



    }    



    public static void f(int x) {



        System.out.print(" " + x);



        if (x < 15) {



            f(2 * x);



        }



    }



}
>> 1 2 4 8 16
Рекурсия без ветвлений, "print на выходе":
public class RecursionPrintOut {
    public static void main(String[] args) {
        f(1);
    }    
    public static void f(int x) {
        if (x < 15) {
            f(2 * x);
        }
        System.out.print(" " + x);
    }
}
>> 16 8 4 2 1


Объяснение рекурсии без ветвлений (данный пример кода проясняет принцип работы предыдущих двух, запустите его и проанализируйте результат):
class RecursionPrintInOutExplanation {
    private static int depth = 0;
    public static void main(String[] args) {
        f(1);
    }
    public static void f(int x) {
        in(x);
        if (check(x)) {
            f(2 * x);
        }
        out(x);
    }
    public static boolean check(int x) {
        spaces();
        System.out.println("(x < 15): " + (x < 15));
        return x < 15;
    }
    public static void in(int x) {
        spaces();
        System.out.println("(" + x + ")->");
        depth++;
    }
    public static void out(int x) {
        depth--;
        spaces();
        System.out.println("<-(" + x + ")");
    }
    private static void spaces() {
        for (int k = 0; k < depth; k++) {
            System.out.print("   ");
        }
    }
}
>> (1)->
>>     (x < 15): true
>>     (2)->
>>         (x < 15): true
>>         (4)->
>>             (x < 15): true
>>             (8)->
>>                 (x < 15): true
>>                 (16)->
>>                      (x < 15): false
>>                 <-(16)
>>             <-(8)
>>         <-(4)
>>     <-(2)
>> <-(1)

АЛГОРИТМ: Числа Фибоначчи.
ИДИОМА: Рекурсия с ветвлением
Числа Фибоначчи (развернутая форма):


public class FibonacciQuiz {



    public static void main(String[] args) {



        f(5);



    }



    public static int f(int x) {



        System.out.print(" " + x);



        if (x == 0) {



            return 0;



        } else if (x == 1 ) {



            return 1;



        } else {



            return  f(x - 2) + f(x - 1);



        }



    }



}
>> 5 3 1 2 0 1 4 2 0 1 3 1 2 0 1

Числа Фибоначчи (компактная форма):
class FibonacciCompact {
    public static void main(String[] args) {
        f(5);
    }
    public static int f(int x) {
        System.out.print(" " + x);
        return (x < 2) ? x : f(x - 2) + f(x - 1);
    }
}
>> 5 3 1 2 0 1 4 2 0 1 3 1 2 0 1
Примечание: компактная форма предложена читателем Achenar.
Примечание: функция f(i) вычисляет i-тое значение чисела Фибоначчи.
Примечание: данный код вычисляет i-тое значение числа Фибоначчи за экспоненциальное время, так же можно вычислять за линейное и логарифмическое.
СИНТАКСИС: тернарная условная операция

Объяснение чисел Фибоначчи:

class FibonacciExplanation {
    private static int depth = 0;
    public static void main(String[] args) {
        f(5);
    }
    public static int f(int x) {
        in(x);
        int result = (x < 2) ? x : f(x - 2) + f(x - 1);
        out(x);
        return result;
    }
    public static void in(int x) {
        spaces();
        System.out.println("(" + x + ")->");
        depth++;
    }
    public static void out(int x) {
        depth--;
    }
    private static void spaces() {
        for (int k = 0; k < depth; k++) 
            System.out.print("    ");
    }
}
>> (5)->
>>       (3)->
>>             (1)->
>>             (2)->
>>                   (0)->
>>                   (1)->
>>       (4)->
>>             (2)->
>>                   (0)->
>>                   (1)->
>>             (3)->
>>                   (1)->
>>                   (2)->
>>                         (0)->
>>                         (1)->


------------Числа Фибоначчи с "вращением"------------
--- Код:
public class FibonacciQuizWithRotation {
    public static void main(String[] args) {
        f(5);
    }
    public static int f(int x) {
        System.out.print(" " + x);
        if (x == 0) {
            return 0;
        } else if (x == 1) {
            return 1;
        } else if (x % 2 == 0) {
            return f(x - 2) + f(x - 1);
        } else {
            return f(x - 1) + f(x - 2);
        }
    }
}

--- Вопросы/Задания:
1) Что выведет при запуске данный пример кода?

-----"Обратные" числа Фибоначчи с "вращением"-----
--- Код:
public class ReverseFibonacciQuizWithRotation {
    public static void main(String[] args) {
        f(5);
    }
    public static int f(int x) {
        int result;
        if (x == 0) {
            result = 0;
        } else if (x == 1) {
            result = 1;
        } else if (x % 2 == 0) {
            result = f(x - 2) + f(x - 1);
        } else {
            result = f(x - 1) + f(x - 2);
        }
        System.out.print(" " + x);
        return result;
    }
}
--- Вопросы/Задания:
1) Что выведет при запуске данный пример кода?


    Лабораторные
    proc.recursion.fib_print_expression 
    Задания лабораторных можно прочитать на этой странице.    


Автор: