>> ZAMYLA: Для того, чтобы понять, рекурсия, вы должны
сначала понять рекурсию.
Имея рекурсию в программных дизайна средств что у вас есть самосправочные
определения.
Рекурсивные структуры данных, например, это структуры данных, которые
включают себя в их определения.
Но сегодня мы собираемся сосредоточиться на рекурсивных функций.
>> Напомним, что функции принимают входы, аргументы, и возвращает значение, как и их
Выход в лице эта схема здесь.
Мы будем думать о поле как тело функция, содержащий набор
инструкции, которые интерпретируют вход и обеспечивают выход.
При более тщательном изучении внутри тела функция может выявить вызовы
другие функции, а также.
Возьмите эту простую функцию, Фу, что занимает одну строку в качестве входных данных и
печатает сколько писем что строка имеет.
Функция STRLEN, для длины строки, называется, выход которого
требуется для вызова Printf.
>> Теперь, то, что делает рекурсивную функцию особенного в том, что он называет себя.
Мы можем представить этот рекурсивный позвонить с этим оранжевой стрелкой
цикл обратно к себе.
Но выполнение себя снова будет только сделать еще один рекурсивный вызов, и
еще и еще.
Но рекурсивные функции не может быть бесконечным.
Они должны положить конец так или иначе, или ваш Программа будет работать вечно.
>> Так что мы должны найти способ разорвать из рекурсивных вызовов.
Базовый вариант Мы называем это.
Когда базовый вариант условие выполняется, функция возвращает без
другой рекурсивный вызов.
Возьмите эту функцию, привет, пустой функции , которая принимает Int N в качестве входных данных.
Базовый вариант стоит на первом месте.
Если п меньше нуля, печати свидания и вернуться Во всех остальных случаях,
Функция будет печатать привет и выполнить рекурсивный вызов.
Еще один звонок к функции привет с уменьшается входное значение.
>> Теперь, даже при том, что мы печатаем привет, функция не будет прекратить пока мы не
вернуть его возвращаемый тип, в этом случае пустоты.
Таким образом, для каждого п, кроме базового варианта, эта функция привет вернется привет
н минус 1.
Так как эта функция является ничтожным, хотя, мы не будет явно тип возвращаемого здесь.
Мы просто выполнить функцию.
Так называя привет (3) будет печатать привет и выполнить привет (2), который выполняет привет (1) один
который выполняет Hi (0), где базовый вариант условие.
Так привет (0) печатает свидания и возвращается.
>> ОК.
Так что теперь мы понимаем основы рекурсивные функции, которые они должны
по меньшей мере один базовый вариант, а также рекурсивный вызов, давайте перейдем к
более значимым примером.
Тот, который не просто вернуть не аннулирует ни на что.
>> Давайте взглянем на факториала Операция используется чаще всего в
вероятностные расчеты.
Факториал п является произведением каждый положительное целое число меньше
и равна п.
Так факторный пять в 5 раз 4 раз 3 раз 2 раз 1, чтобы дать 120.
Четыре факторный в 4 раза 3 раза 2 раз 1 с получением 24.
И то же самое правило применяется любое положительное целое.
>> Итак, как мы могли бы написать рекурсивный функция, которая вычисляет факториал
ряда?
Ну, мы должны определить, как базовый вариант и рекурсивный вызов.
Рекурсивный вызов будет таким же, для всех случаев за основу, кроме
случай, который означает, что мы должны будем найти модель, которая даст нам нашу
Желаемый результат.
>> Для этого примера, посмотрим, как 5 факториала включает умножения 4 по 3 на 2 на 1
И в тот же умножение находится здесь,
Определение 4 факториала.
Итак, мы видим, что 5 факториал всего 5 раз 4 факторный.
Теперь же эта модель применяется до 4 факториал, а?
Да.
Мы видим, что 4 факторный содержит умножение 3 раза 2 раз 1,
Сам же определение, как 3 факториала.
Так 4 факторный равна 4 раза 3 факторный, и так далее и тому подобное нашей
шаблон не прилипает до 1 факториала, которая по определению равна 1.
>> Там нет другой положительный целые оставили.
Поэтому у нас есть образец для наш рекурсивный вызов.
н факторный равна п раз факториал п минус 1.
И наш базовый сценарий?
Это будет просто наше определение 1 факториала.
>> Так что теперь мы можем перейти к написанию код функции.
Для базового варианта, мы будем иметь состояние п равна равна 1, где
мы вернемся 1.
Тогда перейти на рекурсивного вызова, мы вернемся п раз
Факториал п минус 1.
>> Теперь давайте проверим это наше.
Давайте попробуем факториала 4.
За нашей функции он равен в 4 раза факториал (3).
Факториал (3) равна 3 раза факторных (2).
Факториал (2) равна 2 раза факторный (1), которая возвращает 1.
Факториал (2) теперь возвращает 2 раза 1, 2.
Факториал (3) теперь можно вернуться 3 раза 2, 6.
И, наконец, факторный (4) возвращает 4 раза 6, 24.
>> Если возникают какие-либо трудности с рекурсивного вызова, делать вид, что
функция работает уже.
То, что я имею в виду, что вы должны доверять своим рекурсивные вызовы, чтобы вернуться
правильные значения.
Например, если я знаю, что факторный (5) равна 5 раз
факторный (4), я собираюсь верить, что факторный (4) даст мне 24.
Думайте об этом как переменной, если вы будет, как если бы вы уже определены
факториал (4).
Таким образом, для любого факториала (п), это произведение п и
предыдущий факторный.
И это предыдущая факторный получается путем вызова
Факториал п минус 1.
>> Так вот, видите, если вы можете реализовать рекурсивная функция себя.
Загрузите ваш терминал, или run.cs50.net, и написать функцию сумму
, которая принимает число п и возвращает Сумма всех подряд положительный
целые числа от п до 1.
Я выписал суммы некоторых значения, которые помогут вам наш.
Во-первых, выяснить, базовый вариант состояние.
Затем посмотрите на суммы (5).
Можете ли вы выразить ее через другой суммы?
Теперь, что касается суммы (4)?
Как вы можете выразить сумму (4) с точки зрения другой суммы?
>> Если у вас есть сумма (5) и сумма (4) выражается через других сумм, см.
если вы можете определить шаблон для суммы (п).
Если нет, попробуйте несколько других номеров и выражать свои суммы в
условия еще номера.
Выявляя закономерности для дискретных номера, вы хорошо на вашем пути к
выявления образец для любого п.
>> Рекурсия это действительно мощный инструмент, поэтому, конечно, это не ограничивается
математические функции.
Рекурсия может быть использован весьма эффективно при работе с деревьями, например.
Проверьте хватает деревьев для более тщательный анализ, но сейчас
напомнить, что бинарные деревья поиска, в частности, состоят из узлов, каждый
со значением и двух указателей узлов.
Как правило, она представлена родительский узел, имеющий одну строку, указывающую
на левый узел детьми и один в нужное дочернего узла.
Структура бинарного поиска дерево хорошо поддается
к рекурсивного поиска.
Рекурсивный вызов либо переходит в влево или право узел, но более
того, что в дереве короткого замыкания.
>> Допустим, вы хотите выполнить операцию каждый узел в двоичном дереве.
Как вы могли бы пойти по этому поводу?
Ну, вы могли бы написать рекурсивную функция, которая выполняет операцию
на родительском узле и делает рекурсивный позвонить в той же функции,
проходя в левой и правый дочерние узлы.
Например, это функция, Foo, что изменяет значение данного узла и
все его детей к 1.
База случае нулевого причин узлов функция для возврата, указывая
что нет никаких узлов оставили в этом поддереве.
>> Давайте идти через него.
Первый родитель 13.
Мы меняем его значение на 1, а затем вызвать наша функция слева, а
как право.
Функция, Фу, называется слева суб-дерево сначала, так что левая узел
будет переведен на 1 и Foo будет назвать на детей этого узла,
Первый левый, а затем правый, и так далее и тому подобное.
И сказать им, что филиалы не имеют больше детей, так же процесс
будет продолжаться в течение правильных детей до узлы все дерево в не
переведен в 1.
>> Как вы можете видеть, вы не ограничены просто один рекурсивный вызов.
Так же, как многие, как будет получить работу.
Что если у вас на дерево, где каждый узел было трое детей,
Слева, средний, и правильно?
Как бы вы изменить Foo?
Ну, просто.
Просто добавить еще один рекурсивный вызов и пройти в указателе среднего узла.
>> Рекурсия является очень мощным и не говоря элегантно, но это может быть
сложная концепция на первый, так тому и быть пациенту и не торопитесь.
Начните с базового варианта.
Это, как правило, самый простой для выявления, а затем вы можете работать
назад оттуда.
Вы знаете, что вам нужно для достижения ваших базовый вариант, так что может
дать вам несколько советов.
Попробуйте выразить один конкретный случай в условия других случаях, или в подмножеств.
>> Спасибо за просмотр этой короткой.
По крайней мере, теперь вы можете понять шутки, как это.
Меня зовут Zamyla, и это CS50.
>> Возьмите эту функцию, привет, недействительными функция, которая принимает
внутр, п, в качестве входных данных.
Базовый вариант стоит на первом месте.
Если п меньше 0, печати "До свидания" и возвращение.