Как работает рекурсия в си

Рекурсия. Примеры решения задач. Преимущества и недостатки рекурсии

Любая функция (метод) в своем теле может вызывать сама себя. Рекурсия – это такой способ определения функции, при котором результат возврата из функции для данного значения аргумента определяется на основе результата возврата из той же функции для предыдущего (меньшего или большего) значения аргумента.

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

2. Объяснения к реализации задач на рекурсию. Как правильно организовать рекурсивный вызов функции?

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

Чтобы циклический процесс преобразовать в рекурсивный, нужно уметь определить (выделить) три важных момента:

• условие прекращения последовательности рекурсивных вызовов функции. Например, если счетчик или итератор с именем k изменяется от 1 до 10 в возрастающем порядке, то условие прекращения есть достижение значения k =10. Условие прекращения указывается в операторе return ;
• формулу следующего элемента или итератора, который используется в рекурсивном процессе. Эта формула указывается в операторе return ;
• список параметров, которые передаются в рекурсивную функцию. Один из параметров обязательно есть итератор (счетчик) изменяющий свое значение. Другие параметры являются дополнительными, например, ссылка на массив, над которым осуществляется обработка.

3. Поиск суммы элементов массива. Пример

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

Задача. Задан массив чисел A . Разработать рекурсивную функцию, которая находит сумму элементов массива:

где n – количество элементов массива. Программный код функции следующий:

// сумма элементов массива int Sum(int i, int A[], int n) < if (i==n-1) return A[i]; else return A[i]+Sum(i+1,A,n); >

Как видно из примера, в рекурсивную функцию Sum() передается 3 параметра:

• текущее значение итератора i ;
• массив A ;
• количество элементов массива n .

Выход из функции осуществляется, если будет обработан последний элемент массива. Условие прекращения рекурсивного процесса имеет вид:

if (i==n-1) return A[i];

Для суммирования текущего значения A[i] со следующими указывается строка:

return A[i]+Sum(i+1,A,n);

где рекурсивный вызов Sum(i+1, A, n) означает следующее значение массива A . Параметр i+1 указывает, что на следующем уровне вызова рекурсивной функции будет взят следующий после данного элемент массива.

Использование функции Sum() в другом программном коде может быть, например, таким:

int A[] = < 5, 7, 2, -1 >; int n = 4; int sum; sum = Sum(0,A,n); // sum = 13

4. Пример подсчета количества вхождений заданного символа в строке

В данном примере реализована рекурсивная функция Count() , которая определяет количество вхождений заданного символа c в строке s . Функция получает 3 параметра:

• символ c , который нужно сравнить с каждым символом строки s ;
• строка s ;
• дополнительная переменная i , которая есть счетчиком рекурсивного цикла.

Реализация функции Count() следующая:

// подсчет символа c в строке символов s int Count(char c, string s, int i) < if (i==s.length()) // условие окончания рекурсивного процесса - вся строка пройдена return 0; else < if (c == s[i]) // если символ найден return Count(c,s,i+1)+1; // увеличить количество найденных символов на 1 else return Count(c,s,i+1); // иначе, перейти к обработке следующего символа > >

5. Пример нахождения факториала числа – n!

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

Рекурсивный вызов можно организовать двумя способами:

• в порядке возрастания 1, 2, …, n ;
• в порядке убывания n , n -1, …, 2, 1.

В данном примере разработаны две функции, которые находят факториал обоими способами. Программный код функций следующий:

// вычисление факториала - способ 1 int Fact1(int n, int i) < if (i==n) return n; // условие завершения рекурсивного процесса else return i*Fact1(n, i+1); // переход к следующему числу i+1 > // вычисление факториала - способ 2 int Fact2(int n) < if (n==1) return 1; // условие завершения рекурсивного процесса else return n*Fact2(n-1); // переход к предыдущему числу n-1 >

В первую функцию Fact1() передаются 2 параметра. Первый параметр определяет максимально возможное значение n , которое может быть умножено. Второй параметр определяет текущее значение i которое умножается.

Во второй функции Fact2() передается 1 параметр – максимально возможное значение n , принимающее участие в рекурсивном умножении. Второго параметра здесь не нужно, поскольку условие прекращения рекурсивного процесса есть известно и равно 1. В функции Fact2() рекурсивный процесс завершается при n =1.

Использование функций в другом программном коде может быть следующим:

int f; // использование функции Fact1() f = Fact1(5,1); // f = 5! = 120 f = Fact1(7,1); // f = 7! = 5040 f = Fact1(2,1); // f = 2! = 2 // использование функции Fact2() f = Fact2(5); // f = 5! = 120 f = Fact2(8); // f = 8! = 40320

6. Программа нахождения наибольшего общего делителя (алгоритм Евклида). Пример

В примере определяется наибольший общий делитель по формуле Евклида:

Программный код функции следующий:

// наибольший общий делитель по алгоритму Евклида int MaxDiv(int n, int m) < if (n==m) return n; else if (n>m) return MaxDiv(n-m, m); else return MaxDiv(n, m-n); >

Использование функции MaxDiv() может быть следующим:

int md; md = MaxDiv(8, 3); // md = 1 md = MaxDiv(24, 96); // md = 24 md = MaxDiv(9, 15); // md = 3

7. Подсчет количества элементов массива, больших заданного числа. Пример

Демонстрируется метод Count() , возвращающий количество элементов, больших заданного числа num . В метод передается 4 параметра:

• число num , которое нужно сравнивать с каждым элементом массива;
• массив чисел A[ ] ;
• количество элементов массива n ;
• текущее значение счетчика в массиве.

// подсчет количества элементов массива, больших заданного числа int Count(double num, double A[], int n, int i) < if (i==n) return 0; // условие окончания рекурсивного процесса else < if (numreturn Count(num, A, n, i+1) + 1; // добавить 1 к результату, и перейти далее else return Count(num, A, n, i+1); // перейти к следующему элементу массива > >

Использование метода Count() в другом методе

double A[] = < 2.8, 3.5, 1.9, 2.2, 3.6 >; int k; k = Count(2.3, A, 5, 0); // k = 3 k = Count(0.9, A, 5, 0); // k = 5

8. Преимущества использования рекурсии в программах. Пример

Рекурсию часто сравнивают с итерацией. Организация циклического процесса с помощью рекурсии имеет свои преимущества и недостатки.

Можно выделить следующие взаимосвязанные преимущества рекурсии:

• естественность (натуральность) представления сложных, на первый взгляд, алгоритмов;
• рекурсивный алгоритм более читабелен в сравнении с итерационным;
• для многих распространенных задач рекурсию более легко реализовать чем итерацию. Рекурсия хорошо подходит для реализации алгоритмов обхода списков, деревьев, анализаторов выражений, комбинаторных задач и т.д.

Недостатки рекурсии состоят в следующем:

• по сравнению с итерацией многоразовый вызов рекурсивной функции требует больше времени. Это связано с тем, что при вызове рекурсивного метода его параметры копируются в стек. При завершении вызова рекурсивной функции предыдущие значения параметров вытягиваются из стека, что приводит к лишним операциям. Итерационный алгоритм для той же задачи работает быстрее;
• если рекурсивная функция содержит большие объемы локальных внутренних переменных и большое количество параметров, то использование рекурсии не является эффективным. Это связано с тем, что для каждого рекурсивного вызова нужно делать копии этих переменных и параметров. При большом количестве рекурсивных вызовов это приведет к чрезмерному использованию памяти.

Связанные темы

Рекурсия в С++

Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Самый простой вариант увидеть рекурсию – это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив. Таким образом, камера будет записывать изображение экрана компьютера, и выводить его же на этот экран, получится что-то вроде замкнутого цикла. В итоге мы будем наблюдать нечто похожее на тоннель.

В программировании рекурсия тесно связана с функциями, точнее именно благодаря функциям в программировании существует такое понятие как рекурсия или рекурсивная функция. Простыми словами, рекурсия – определение части функции (метода) через саму себя, то есть это функция, которая вызывает саму себя, непосредственно (в своём теле) или косвенно (через другую функцию). Типичными рекурсивными задачами являются задачи: нахождения n!, числа Фибоначчи. Такие задачи мы уже решали, но с использованием циклов, то есть итеративно. Вообще говоря, всё то, что решается итеративно можно решить рекурсивно, то есть с использованием рекурсивной функции. Всё решение сводится к решению основного или, как ещё его называют, базового случая. Существует такое понятие как шаг рекурсии или рекурсивный вызов. В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение. Разработаем программу, в которой объявлена рекурсивная функция, вычисляющая n!

// factorial.cpp: определяет точку входа для консольного приложения. #include "stdafx.h" #include using namespace std; unsigned long int factorial(unsigned long int);// прототип рекурсивной функции int i = 1; // инициализация глобальной переменной для подсчёта кол-ва рекурсивных вызовов unsigned long int result; // глобальная переменная для хранения возвращаемого результата рекурсивной функцией int main(int argc, char* argv[]) < int n; // локальная переменная для передачи введенного числа с клавиатуры cout > n; cout unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! < if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout 

// factorial.cpp: определяет точку входа для консольного приложения. #include using namespace std; unsigned long int factorial(unsigned long int);// прототип рекурсивной функции int i = 1; // инициализация глобальной переменной для подсчёта кол-ва рекурсивных вызовов unsigned long int result; // глобальная переменная для хранения возвращаемого результата рекурсивной функцией int main(int argc, char* argv[]) < int n; // локальная переменная для передачи введенного числа с клавиатуры cout > n; cout unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! < if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout 

В строках 7, 9, 21 объявлен тип данных unsigned long int , так как значение факториала возрастает очень быстро, например уже 10! = 3 628 800. Если не хватит размера типа данных, то в результате мы получим совсем не правильное значение. В коде объявлено больше операторов, чем нужно, для нахождения n!. Это сделано для того, чтобы, отработав, программа показала, что происходит на каждом шаге рекурсивных вызовов. Обратите внимание на выделенные строки кода, строки 23, 24, 28 — это рекурсивное решение n!. Строки 23, 24 являются базовым решением рекурсивной функции, то есть, как только значение в переменной f будет равно 1 или 0 (так как мы знаем, что 1! = 1 и 0! = 1), прекратятся рекурсивные вызовы, и начнут возвращаться значения, для каждого рекурсивного вызова. Когда вернётся значение для первого рекурсивного вызова, программа вернёт значение вычисляемого факториала. В строке 28 функция factorial() вызывает саму себя, но уже её аргумент на единицу меньше. Аргумент каждый раз уменьшается, чтобы достичь частного решения. Результат работы программы (см. Рисунок 1).

CppStudio.com

Enter n!: 5 Step 1 Result= 0 Step 2 Result= 0 Step 3 Result= 0 Step 4 Result= 0 5!=120

Рисунок 1 — Рекурсия в С++

По результату работы программы хорошо виден каждый шаг и результат на каждом шаге равен нулю, кроме последнего рекурсивного обращения. Необходимо было вычислить пять факториал. Программа сделала четыре рекурсивных обращения, на пятом обращении был найден базовый случай. И как только программа получила решение базового случая, она порешала предыдущие шаги и вывела общий результат. На рисунке 1 видно всего четыре шага потому, что на пятом шаге было найдено частное решение, что в итоге вернуло конечное решение, т. е. 120. На рисунке 2 показана схема рекурсивного вычисления 5!. В схеме хорошо видно, что первый результат возвращается, когда достигнуто частное решение, но никак не сразу, после каждого рекурсивного вызова.

Рисунок 2 — Рекурсия в С++

Итак, чтобы найти 5! нужно знать 4! и умножить его на 5; 4! = 4 * 3! и так далее. Согласно схеме, изображённой на рисунке 2, вычисление сведётся к нахождению частного случая, то есть 1!, после чего по очереди будут возвращаться значения каждому рекурсивному вызову. Последний рекурсивный вызов вернёт значение 5!.

Переделаем программу нахождения факториала так, чтобы получить таблицу факториалов. Для этого объявим цикл for , в котором будем вызывать рекурсивную функцию.

// factorial.cpp: определяет точку входа для консольного приложения. #include "stdafx.h" #include using namespace std; unsigned long int factorial(unsigned long int);// прототип рекурсивной функции int i = 1; // инициализация глобальной переменной для подсчёта кол-ва рекурсивных вызовов unsigned long int result; // глобальная переменная для хранения возвращаемого результата рекурсивной функцией int main(int argc, char* argv[]) < int n; // локальная переменная для передачи введенного числа с клавиатуры cout > n; for (int k = 1; k system("pause"); return 0; > unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! < if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout 

// factorial.cpp: определяет точку входа для консольного приложения. #include using namespace std; unsigned long int factorial(unsigned long int);// прототип рекурсивной функции int i = 1; // инициализация глобальной переменной для подсчёта кол-ва рекурсивных вызовов unsigned long int result; // глобальная переменная для хранения возвращаемого результата рекурсивной функцией int main(int argc, char* argv[]) < int n; // локальная переменная для передачи введенного числа с клавиатуры cout > n; for (int k = 1; k return 0; > unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! < if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout 

В строках 16 — 19 объявлен цикл, в котором вызывается рекурсивная функция. Всё ненужное в программе закомментированно. Запустив программу, нужно ввести значение, до которого необходимо вычислить факториалы. Результат работы программы показан на рисунке 3.

CppStudio.com

Enter n!: 14 1!=1 2!=2 3!=6 4!=24 5!=120 6!=720 7!=5040 8!=40320 9!=362880 10!=3628800 11!=39916800 12!=479001600 13!=6227020800 14!=87178291200

Рисунок 3 — Рекурсия в С++

Теперь видно, насколько быстро возрастает факториал, кстати говоря, уже результат 14! не правильный, это и есть последствия нехватки размера типа данных. Правильное значение 14! = 87178291200.

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

// fibonacci.cpp: определяет точку входа для консольного приложения. #include "stdafx.h" #include // библиотека для форматирования выводимой информации на экран #include using namespace std; unsigned long fibonacci(unsigned long);// прототип рекурсивной функции поиска чисел из ряда Фибоначчи int main(int argc, char* argv[]) < unsigned long entered_number; cout > entered_number; for (int counter = 1; counter unsigned long fibonacci(unsigned long entered_number) // функция принимает один аргумент < if ( entered_number == 1 || entered_number == 2) // частный случай return (entered_number -1); // ряд чисел Фибоначчи всегда начинается с 0, 1, . return fibonacci(entered_number-1) + fibonacci(entered_number-2); // формула поиска н-го числа, например найти восьмое по счёту число, и оно равно 7-е + 6-е >

// fibonacci.cpp: определяет точку входа для консольного приложения. #include // библиотека для форматирования выводимой информации на экран #include using namespace std; unsigned long fibonacci(unsigned long);// прототип рекурсивной функции поиска чисел из ряда Фибоначчи int main(int argc, char* argv[]) < unsigned long entered_number; cout > entered_number; for (int counter = 1; counter unsigned long fibonacci(unsigned long entered_number) // функция принимает один аргумент < if ( entered_number == 1 || entered_number == 2) // частный случай return (entered_number -1); // ряд чисел Фибоначчи всегда начинается с 0, 1, . return fibonacci(entered_number-1) + fibonacci(entered_number-2); // формула поиска н-го числа, например найти восьмое по счёту число, и оно равно 7-е + 6-е >

В строке 6 подключена библиотека для того, чтобы воспользоваться функцией setw() , которая в свою очередь выравнивает первый столбец чисел, то есть номера. Как мы можем заметить, сначала числа однозначные от 1 – 9, а потом идут двузначные. Если убрать данную функцию, то произойдет сдвиг влево чисел от 1 и до 9. Результат работы программы (см. Рисунок 4).

CppStudio.com

Enter number from the Fibonacci series: 30 1 = 0 2 = 1 3 = 1 4 = 2 5 = 3 6 = 5 7 = 8 8 = 13 9 = 21 10 = 34 11 = 55 12 = 89 13 = 144 14 = 233 15 = 377 16 = 610 17 = 987 18 = 1597 19 = 2584 20 = 4181 21 = 6765 22 = 10946 23 = 17711 24 = 28657 25 = 46368 26 = 75025 27 = 121393 28 = 196418 29 = 317811 30 = 514229

Рисунок 4 — Рекурсия в С++

Решение сводится к разбиению сложной задачи к двум более простым. Например, чтобы найти третье число из ряда Фибоначчи, необходимо сначала найти первое и второе, а потом сложить их. Первое число является частным случаем и равно 0 (нулю), второе число также является частным случаем и равно 1. Следовательно, третье число из ряда Фибоначчи равно сумме первого и второго = 1. Приблизительно так же рассуждала запрограммированная нами рекурсивная функция поиска чисел ряда Фибоначчи.

Разработаем ещё одну рекурсивную программу, решающую классическую задачу — «Ханойская башня». Даны три стержня, на одном из которых находится стопка n-го количества дисков, причём диски имеют не одинаковый размер (диски различного диаметра) и расположены таким образом, что по мере прохождения, сверху вниз по стержню диаметр дисков постепенно увеличивается. То есть диски меньшего размера должны лежать только на дисках большего размера. Необходимо переместить эту стопку дисков с начального стержня на любой другой из двух оставшихся (чаще всего это третий стержень). Один из стержней использовать как вспомогательный. Перемещать можно только по одному диску, при этом диск большего размера никогда не должен находиться над диском меньшего размера.

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

Программу надо написать для n-го количества дисков. Так как мы решаем данную задачу рекурсивно, то для начала необходимо найти частные случаи решения. В данной задаче частный случай только один – это когда необходимо переместить всего один диск, и в этом случае даже вспомогательный стержень не нужен, но на это просто не обращаем внимания. Теперь необходимо организовать рекурсивное решение, в случае, если количество дисков больше одного. Введём некоторые обозначения, для того, чтоб не писать лишнего:

— стержень, на котором изначально находятся диски (базовый стержень);
— вспомогательный или промежуточный стержень;
— финальный стержень – стержень, на который необходимо переместить диски.

Далее, при описании алгоритма решения задачи будем использовать эти обозначения. Чтобы переместить три диска с на нам необходимо сначала переместить два диска с на а потом переместить третий диск(самый большой) на , так как свободен.

Для того, чтобы переместить n дисков с на нам необходимо сначала переместить n-1 дисков с на а потом переместить n-й диск(самый большой) на , так как свободен. После этого необходимо переместить n-1 дисков с на , при этом использовать стержень как вспомогательный. Эти три действия и есть весь рекурсивный алгоритм. Этот же алгоритм на псевдокоде:
n-1 переместить на
n переместить на
n-1 переместить с на , при этом использовать как вспомогательный

// hanoi_tower.cpp: определяет точку входа для консольного приложения. // Программа, рекурсивно решающая задачу "Ханойская башня" #include "stdafx.h" #include #include using namespace std; void tower(int, int, int, int); // объявление прототипа рекурсивной функции int count = 1; // глобальная переменная для подсчёта количества шагов int _tmain(int argc, _TCHAR* argv[]) < cout > number; cout > basic_rod; cout > final_rod; int help_rod; // блок определения номера вспомогательного стержня, анализируя номера начального и финального стержня if (basic_rod != 2 && final_rod != 2 ) help_rod = 2; else if (basic_rod != 1 && final_rod != 1 ) help_rod = 1; else if (basic_rod != 3 && final_rod != 3 ) help_rod = 3; tower(// запуск рекурсивной функции решения задачи Ханойских башен number, // переменная, хранящая количество дисков, которые надо переместить basic_rod, // переменная, хранящая номер стержня, на котором диски будут находится изначально help_rod , // переменная, хранящая номер стержня, который используется, как вспомогательный final_rod); // переменная, хранящая номер стержня, на который необходимо переместить диски system("pause"); return 0; > void tower(int count_disk, int baza, int help_baza, int new_baza) < if ( count_disk == 1) // условие завершения рекурсивных вызовов < cout " else < tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный >>

// hanoi_tower.cpp: определяет точку входа для консольного приложения. // Программа, рекурсивно решающая задачу "Ханойская башня" #include #include using namespace std; void tower(int, int, int, int); // объявление прототипа рекурсивной функции int count = 1; // глобальная переменная для подсчёта количества шагов int main() < cout > number; cout > basic_rod; cout > final_rod; int help_rod; // блок определения номера вспомогательного стержня, анализируя номера начального и финального стержня if (basic_rod != 2 && final_rod != 2 ) help_rod = 2; else if (basic_rod != 1 && final_rod != 1 ) help_rod = 1; else if (basic_rod != 3 && final_rod != 3 ) help_rod = 3; tower(// запуск рекурсивной функции решения задачи Ханойских башен number, // переменная, хранящая количество дисков, которые надо переместить basic_rod, // переменная, хранящая номер стержня, на котором диски будут находится изначально help_rod , // переменная, хранящая номер стержня, который используется, как вспомогательный final_rod); // переменная, хранящая номер стержня, на который необходимо переместить диски return 0; > void tower(int count_disk, int baza, int help_baza, int new_baza) < if ( count_disk == 1) // условие завершения рекурсивных вызовов < cout " else < tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный >>

Enter of numbers of disks: 3 Enter the number of basic rod: 1 Enter the number of final rod: 3 1) 1 -> 3 2) 1 -> 2 3) 3 -> 2 4) 1 -> 3 5) 2 -> 1 6) 2 -> 3 7) 1 -> 3

function look_for_key(main_box) < let pile = main_box.make_a_pile_to_look_through(); while (pile is not empty) < box = pile.grab_a_box(); for (item in box) < if (item.is_a_box()) < pile.append(item) >else if (item.is_a_key()) < console.log("found the key!") >> > >

function look_for_key(box) < for (item in box) < if (item.is_a_box()) < look_for_key(item); >else if (item.is_a_key()) < console.log("found the key!") >> >

// WARNING: This function contains an infinite loop! function countdown(i) < console.log(i) countdown(i - 1) >countdown(5); // This is the initial call to the function.

function countdown(i) < console.log(i) if (i else < // recursive case countdown(i - 1) >> countdown(5); // This is the initial call to the function.

function fact(x) < if (x == 1) < return 1; >else < return x * fact(x-1); >>