пытаясь понять рекурсию в C

Question

Я пытаюсь понять, как работает следующий C-код:

int factorial(int n) {
   int result;
   if(n==0){
       result=1;
    }else{
       result = n * factorial(n-1);
   }
   return result;
}

Я понимаю, что вывод является факториалом n.Думаю, я пытаюсь понять, использует ли этот пример рекурсии оператор if в качестве причины для рекурсии.И может ли рекурсия для этого также выполняться с циклом for вместо if?Или я полностью упускаю суть?

Answer 1

Думаю, я пытаюсь понять, использует ли этот пример рекурсии оператор if в качестве причины для рекурсии.

причина для рекурсии - это функциязовет себя.Условие if (n == 0) говорит нам, когда остановить повторение.

Если мы вызываем factorial(3), рекурсия выглядит примерно так:

factorial(3):
  return 3 * factorial(2): -----------+
     return 2 * factorial(1); ------+ |
       return 1 * factorial(0); --+ | |
         return 1;                | | |
       1; <-----------------------+ | |
     2; <---------------------------+ |
  6; <--------------------------------+

И может ли рекурсия для этого также выполняться с циклом for вместо if?

В этом случае вы бы не использовали цикл - рекурсия - это тип цикла сам по себе.

Для вычислений факториалов, чисел Фибоначчи и т. Д. Я буду утверждать, что итерационный алгоритм (цикл) превосходит рекурсивный алгоритм:

int factorial_iter( int n )
{
  int result = 1;
  while ( n )
    result *= n--;
  return result;
}

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

n! = n * n-1!, 0! = 1

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

factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial( n - 1 )

Все, что вы можете решить рекурсивно, вы можете решить итеративно, хотя некоторые решения (быстрая сортировка, обходы деревьев и т. Д.)Гораздо проще реализовать рекурсивно.

Например, обход дерева порядка можно записать как

 /**
  * Perform an inorder traversal by
  * visiting the left subtree, then the root,
  * then the right subtree.
  */
 void inorder( node_type *t )
 {
   if ( !t )
     return;

   inorder( t->left );
   do_something_with( t->data );
   inorder( t->right );
 }

Это на 1043 * намного проще, чем пытаться написать цикл для посещения.все узлы в правильном порядке.

Answer 2

Думайте об этом так:

• Факториал 5 равен (5 * факториал 4)
• Факториал 4 равен (4 * факториал 3)
• Факториал 3 равен (3 * факториал 2)
• Факториал 2 равен (2 * факториал 1)
• Факториал 1 равен 1

Это то, что делает ваш код.Когда его запрашивают fact(1), он возвращает 1. В противном случае он возвращает n раз fact(n-1);повторять (рекурсировать) по мере необходимости