Пример рекурсии C ++ | Программа рекурсии в учебнике C ++

Пример рекурсии C ++ | Программа рекурсии в C ++ Сегодняшняя тема — это учебник. Когда функция вызывает себя, это называется рекурсией . Функция, которая вызывает саму функцию, известна как рекурсивная функция . Основная цель рекурсии — разбить большую проблему на меньшую. Обычно предоставляются базовые решения, а затем мы шаг за шагом выражаем решение более крупной проблемы в терминах этого базового решения. Важно добавить базовый случай, потому что, если мы не добавим базовый вариант, рекурсия никогда не остановится.

Пример рекурсии C ++

Рекурсия — это процесс, в котором функция вызывает себя прямо или косвенно, называется рекурсией, а соответствующая функция называется рекурсивной функцией. Используя рекурсивный алгоритм, можно довольно легко решить некоторые проблемы. Примерами таких проблем являются Ханойские башни (TOH), обход дерева Inorder/Preorder/Postorder , DFS графа и т. Д.

# Какое базовое условие в рекурсии?

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

 int fact (int n) {if (n  

В приведенном выше примере определен базовый вариант для n

Рекурсия продолжается до тех пор, пока не будет выполнено какое-либо условие, чтобы остановить ее.

Если мы хотим Чтобы предотвратить бесконечную рекурсию, можно использовать оператор if… else (или аналогичный подход), когда одна ветвь выполняет рекурсивный вызов, а другие - нет.

# Как решить конкретную проблему с помощью рекурсии?

Идея состоит в том, чтобы представляют проблему с точки зрения одной или нескольких меньших проблем и добавляют одно или несколько базовых условий, останавливающих рекурсию.

Например, мы вычисляем факториал n, если мы знаем факториал (n-1). Базовым случаем для факториала будет n = 0. Мы возвращаем 1, когда n = 0.

Есть два типа рекурсий.

  1. Прямая рекурсия
  2. Косвенная рекурсия

# Прямая рекурсия

Когда функция вызывает сама себя, это называется прямой рекурсией.

# Непрямая рекурсия

Когда функция вызывает другую функцию, и эта функция вызывает первую функцию, мы называем это косвенной рекурсией.

Например, функция A вызывает функцию B, а функция B вызывает функцию A.

# Синтаксис рекурсивных функций

 return_type имя_функции {имя_функции ();} int main () {имя_функции ();}  

# Программа для серии Фибоначчи с использованием рекурсии в C ++

Напишите программу для печати рядов Фибоначчи с использованием рекурсии в C ++.

 #include  с использованием пространства имен std; void fib (int); int main () {int n;  cout > n;  фиб (п);  return 0;} void fib (int n) {int a = 0, b = 1, c, i;  cout  

См. следующий результат.

# Факторное число с использованием рекурсии в C ++

См. Следующую программу.

 #include  с использованием пространства имен std; int rec (int); main () {int a, fact;  cout > a;  fact = rec (a);  cout  

См. следующий результат.

Предположим, пользователь ввел 5, которое передается в функцию rec () .

  1. В первом Функция rec () , проверьте выражение внутри оператора if. Выполняется инструкция return (f) , которая вызывает вторую функцию rec () , и передается аргумент x-1, , что равно 4.
  2. Во второй функции rec () проверьте выражение внутри оператора if, истинное. Выполняется инструкция return (f) , которая вызывает третью функцию rec () , и передается аргумент x-1, который равен 3.
  3. В третьей функции rec () проверьте выражение внутри оператора if. Выполняется инструкция return (f) , которая вызывает четвертую функцию, и передается аргумент x-1, что равно 2.
  4. В четвертой функции rec () проверьте выражение внутри оператора if. Выполняется инструкция return (f) , которая вызывает четвертую функцию, и передается аргумент x-1, который равен 1.
  5. В пятой функции rec () проверьте выражение внутри оператора if, если оно ложно. Выполняется инструкция return 1 .
  6. Итак, вот как мы получаем 5 * 4 * 3 * 2 * 1 = 120.

Наконец, пример рекурсии C ++ | Программа рекурсии в C ++ Учебник окончен.

Оцените статью
nanomode.ru
Добавить комментарий