Рубрики

Рекурсивные функции

Рекурсия :

В терминах программирования рекурсивная функция может быть определена как подпрограмма, которая вызывает себя прямо или косвенно.

Используя рекурсивный алгоритм, некоторые проблемы могут быть решены довольно легко. Towers of Hanoi (TOH) — одно из таких упражнений в программировании. Попробуйте написать итерационный алгоритм для TOH. Более того, каждая рекурсивная программа может быть написана с использованием итерационных методов (Refer Data Structures by Lipschutz).

Математически рекурсия помогает легко решить несколько головоломок.

Например, обычный вопрос интервью,

В группе из N человек каждый человек пожмет руку друг другу только один раз. Всего сколько рукопожатий произойдет?

Решение:

Его можно решить разными способами, графами, рекурсией и т. Д. Посмотрим, насколько рекурсивно это можно решить.

Есть N человек. Каждый человек пожимает руку друг другу только один раз. Учитывая N-го человека, он должен пожать руку (N-1) людям. Теперь проблема сводится к небольшому количеству (N-1) человек. Принимая T N в качестве общего рукопожатия, он может быть сформулирован рекурсивно.

T N = (N-1) + T N-1 [T 1 = 0, т. Е. Последний человек уже обменялся рукопожатием с каждым]

Его рекурсивное решение дает арифметический ряд, который можно оценить как N (N-1) / 2.

Упражнение: В группе из N пар только один пол (мужской или женский) может пожать руку каждому. Сколько рукопожатий случится?

Обычно рекурсивные программы приводят к плохим временным сложностям. Примером является ряд Фибоначчи. Временная сложность вычисления n-го числа Фибоначчи с использованием рекурсии составляет приблизительно 1,6 n . Это означает, что тот же компьютер занимает почти 60% больше времени для следующего числа Фибоначчи. Рекурсивный алгоритм Фибоначчи имеет перекрывающиеся подзадачи. Существуют и другие методы, такие как динамическое программирование, для улучшения таких перекрывающихся алгоритмов.

Однако несколько алгоритмов (например, сортировка слиянием, быстрая сортировка и т. Д.) Приводят к оптимальной временной сложности с использованием рекурсии.

Базовый вариант:

Одним из критических требований рекурсивных функций является точка завершения или базовый случай. Каждая рекурсивная программа должна иметь базовый вариант, чтобы убедиться, что функция завершится. Отсутствие базового варианта приводит к неожиданному поведению.

Различные способы написания рекурсивных функций

Функция сама вызывает: (прямой путь)

Большинство из нас знает по крайней мере два разных способа написания рекурсивных программ. Ниже приведены башни Ханойского кодекса. Это пример прямого звонка.

С

#include<stdio.h>

  
// Предполагая, что n-й диск является нижним (обратный отсчет)

void tower(int n, char sourcePole, char destinationPole, char auxiliaryPole)

{

   // Базовый случай (условие завершения)

   if(0 == n)

     return;

  

   // Переместить первые n-1 диски с полюса источника

   // к вспомогательному полюсу, используя пункт назначения как

   // временный столб

   tower(n-1, sourcePole, auxiliaryPole,

      destinationPole);

  

    // Переместить оставшийся диск из источника

   // полюс к полюсу назначения

   printf("Move the disk %d from %c to %c\n"

    n,sourcePole, destinationPole);

  

   // Переместить n-1 диски из вспомогательных (теперь исходных)

   // полюс к полюсу назначения, используя исходный полюс как

   // временный (вспомогательный) столб

   tower(n-1, auxiliaryPole, destinationPole,

     sourcePole);

}

  

int main()

{

   tower(3, 'S', 'D', 'A');

     

   return 0;

}

Джава

// Предполагается, что n-й диск
// нижний диск (обратный отсчет)

class GFG {

      

static void tower(int n, char sourcePole,

                  char destinationPole, char auxiliaryPole)

{

    // Базовый случай (условие завершения)

    if (0 == n)

    return;

  

    // Переместить первые n-1 диски с полюса источника

    // к вспомогательному полюсу, используя пункт назначения как

    // временный столб

    tower(n - 1, sourcePole, auxiliaryPole,

                          destinationPole);

  

    // Переместить оставшийся диск из источника

    // полюс к полюсу назначения

    System.out.printf("Move the disk %d from %c to %c\n",

                         n, sourcePole, destinationPole);

  

    // Переместить n-1 диски из вспомогательных (теперь исходных)

    // полюс к полюсу назначения, используя исходный полюс как

    // временный (вспомогательный) столб

    tower(n - 1, auxiliaryPole, destinationPole, sourcePole);

}

  

public static void main(String[] args)

{

    tower(3, 'S', 'D', 'A');

}
}

  
// Этот код предоставлен Смитой Динеш Семвал.

python3

# Предполагая, что n-й диск
# нижний диск (обратный отсчет)

def tower(n, sourcePole, destinationPole, auxiliaryPole):

  

    # Базовый случай (условие завершения)

    if(0 == n):

        return

      

    # Переместить первые n-1 дисков

    # от полюса источника

    # к вспомогательному полюсу

    # используя пункт назначения как

    # временный столб

    tower(n-1, sourcePole, auxiliaryPole, destinationPole)

      

    # Переместить оставшиеся

    # диск из источника

    # полюс к полюсу назначения

    print("Move the disk",sourcePole,"from",sourcePole,"to",destinationPole)

      

    # Переместить диски n-1 из

    # вспомогательный (теперь источник)

    # полюс к полюсу назначения

    # используя полюс источника как

    # временный (вспомогательный) столб

    tower(n-1, auxiliaryPole, destinationPole,sourcePole)

  

  
# Код драйвера

tower(3, 'S', 'D', 'A')

C #

// Предполагается, что n-й диск является нижним
// (обратный отсчет)

using System;

  

class GFG {

       

    static void tower(int n, char sourcePole,

                        char destinationPole, 

                          char auxiliaryPole)

    {

          

        // Базовый случай (условие завершения)

        if (0 == n)

            return;

       

        // Переместить первые n-1 диски из источника

        // полюс к вспомогательному полюсу, используя

        // пункт назначения как временный полюс

        tower(n - 1, sourcePole, auxiliaryPole,

                              destinationPole);

       

        // Переместить оставшийся диск из источника

        // полюс к полюсу назначения

        Console.WriteLine("Move the disk " + n 

                + "from " + sourcePole + "to " 

                           + destinationPole);

       

        // Перемещаем n-1 диски из вспомогательных

        // (сейчас источник) полюс к месту назначения

        // полюс, используя исходный полюс в качестве временного

        // (вспомогательный) полюс

        tower(n - 1, auxiliaryPole, 

                  destinationPole, sourcePole);

    }

      

    // Код драйвера

    public static void Main()

    {

        tower(3, 'S', 'D', 'A');

    }

}

   
// Этот код предоставлен Anant Agarwal.

PHP

<?php
// Предполагается, что n-й диск
// нижний диск (обратный отсчет)

  

function tower($n, $sourcePole

               $destinationPole

               $auxiliaryPole)

{

      

    // Базовый вариант

    // (условие завершения)

    if(0 == $n)

        return;

      

    // Переместить первые n-1 дисков

    // от исходного полюса до

    // использование вспомогательного полюса

    // назначение как временное

    // столб

    tower($n - 1, $sourcePole

          $auxiliaryPole

          $destinationPole);

      

    // Переместить оставшиеся

    // диск из источника

    // полюс к полюсу назначения

    echo "Move the disk ", $n

         " from ", $sourcePole

         " to ", $destinationPole

                            "\n";

      

    // Переместить диски n-1 из

    // вспомогательный (теперь источник)

    // полюс к полюсу назначения

    // используя полюс источника как

    // временный (вспомогательный) столб

    tower($n - 1, $auxiliaryPole

          $destinationPole

          $sourcePole);

}

  
// Код драйвера

tower(3, 'S', 'D', 'A');

  
// Этот код предоставлен Ajit.
?>


Выход :

Move the disk 1 from S to D
Move the disk 2 from S to A
Move the disk 1 from D to A
Move the disk 3 from S to D
Move the disk 1 from A to S
Move the disk 2 from A to D
Move the disk 1 from S to D

Временная сложность TOH может быть рассчитана путем формулировки количества ходов.

Нам нужно переместить первые диски N-1 из исходного в вспомогательное и из вспомогательного в целевое, т.е. первые диски N-1 требуют двух перемещений. Еще один ход последнего диска от источника до места назначения. Математически это может быть определено рекурсивно.

М Н = 2М Н-1 + 1.

Мы можем легко решить вышеупомянутое рекурсивное соотношение (2 N -1), которое является экспоненциальным.

Рекурсия с использованием взаимного вызова функции: (косвенный путь)

Непрямой звонок. Хотя функция [funA ()] наименее практичная, она может вызывать другую функцию [funB ()], которая в свою очередь вызывает бывшую функцию [funA ()]. В этом случае обе функции должны иметь базовый вариант.

Защитное программирование:

Мы можем комбинировать методы защитного кодирования с рекурсией для изящной функциональности приложения. Обычно рекурсивное программирование не допускается в приложениях, критически важных для безопасности, таких как управление полетом, мониторинг состояния и т. Д. Однако можно использовать метод статического счета, чтобы избежать неконтролируемых вызовов (НЕ в системах, критичных для безопасности, может использоваться в мягких системах реального времени). ,

void recursive(int data)

{

   static callDepth;

   if(callDepth > MAX_DEPTH)

      return;

  

   // Увеличить глубину звонка

   callDepth++;

  

   // делаем другую обработку

   recursive(data);

  

   // делаем другую обработку

   // Уменьшаем глубину звонка

   callDepth--;

}

Глубина callDepth зависит от размера кадра стека функции и максимального размера стека.

Рекурсия с использованием указателей на функции: (косвенный путь)

Рекурсия также может быть реализована с помощью указателей функций. Примером является обработчик сигналов в системах жалоб POSIX. Если обработчик вызывает такое же событие, из-за которого вызывается обработчик, функция будет повторно введена.


Статьи по Теме:

Спасибо Venki за написание вышеуказанного поста. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Рекурсивные функции

0.00 (0%) 0 votes