Ниже на пяти языках программирования записан рекурсивный алгоритм F.
| Бейсик | Python |
|---|---|
SUB F(n) IF n > 0 THEN PRINT "*" F(n - 1) F(n \ 3) END IF END SUB
| def F(n): if n > 0: print("*") F(n - 1) F(n // 3)
|
| Алгоритмический язык | Паскаль |
алг F(цел n) нач если n > 0 то вывод "*" F(n - 1) F(div(n, 3)) все кон | procedure F(n: integer); begin if n > 0 then begin writeln('*'); F(n - 1); F(n div 3) end end |
| Си | |
void F(int n) { if (n > 0) { printf("*"); F(n - 1); F(n / 3); } }
| |
Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(6)?
Рассмотрим структуру вызова функций.
F(6)
{
F(5)
F(2)
{
F(4)
F(1)
F(1)
F(0)
{
F(3)
F(1)
F(0)
F(0)
F(0)
F(0)
{
F(2)
F(1)
F(0)
{
F(1)
F(0)
{
F(0)
}
}
}
}
}
}
Число напечатанных «звёздочек» равно числу вызовов функции F(n) с аргументом не равным нулю, то есть равно 11.
Ответ: 11.
F(6)
{
F(5)
F(2)
{
F(4)
F(1)
F(1) - откуда эта единица
F(0)
{
F(3)
F(1)
F(0)
F(0)
F(0)
F(0)
{
F(2)
F(1)
F(0)
{
F(1)
F(0)
{
F(0)
Поясняем: F(5) вызывает F(4) и F(1), а F(2) вызывает F(1) и F(0).