16. Рекурсивные алгоритмы

Демонстрационный вариант ЕГЭ 2019 г. – задание №11

Ниже на пяти языках программирования записан рекурсивный алгоритм F.

Бейсик

SUB F(n)
  IF n > 0 THEN
    F(n - 1)
    PRINT n
    F(n - 2)
  END IF
END SUB

Python

def F(n):
    if n > 0:
        F(n - 1)
        print(n)
        F(n - 2)

Алгоритмический язык

алг F(цел n)
нач
если n > 0 то
  F(n - 1)
  вывод n
  F(n - 2)
все
кон

Паскаль

procedure F(n: integer);
begin
  if n > 0 then
  begin
    F(n - 1);
    write(n);
    F(n - 2)
  end
end;

С++

void F(int n){
 if (n > 0){
   F(n - 1);
   std::cout << n;
   F(n - 2);
 }
}

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

Демонстрационный вариант ЕГЭ 2018 г. – задание №11

Ниже на пяти языках программирования записан рекурсивный алгоритм F.

Бейсик

SUB F(n)
  IF n > 0 THEN
   PRINT n
   F(n - 3)
   F(n \ 3)
  END IF
END SUB

Python

def F(n):
  if n > 0:
   print(n)
   F(n - 3)
   F(n // 3)

Алгоритмический язык

алг F(цел n)
нач
  если n > 0 то
   вывод n
   F(n - 3)
   F(div(n, 3))
  все
кон

Паскаль

procedure F(n: integer);
begin
  if n > 0 then
  begin
   write(n);
   F(n - 3);
   F(n div 3)
  end
end;

С++

void F(int n){
  if (n > 0){
   std::cout <<n;
   F(n - 3);
   F(n / 3);
  }
}

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

Ниже на пяти языках программирования записан рекурсивный алгоритм F.

Бейсик

DECLARE SUB F(n)
SUB F(n)
	IF n > 2 THEN
		PRINT n
		F(n - 3)
		F(n – 4)
	END IF
END SUB

Python

def F(n):
	if n > 2:
		print(n)
		F(n - 3)
		F(n – 4)

Алгоритмический язык

алг F(цел n)
нач
	если n > 2 то
		вывод n, нс
		F(n - 3)
		F(n – 4)
	все
кон

Паскаль

procedure F(n: integer);
begin
	if n > 2 then begin
		writeln(n);
		F(n - 3);
		F(n – 4)
	end
end;

Си

void F(int n) {
	if (n > 2) {
		printf("%d\n", n);
		F(n - 3);
		F(n – 4);
	}
}

Чему равна сумма напечатанных на экране чисел при выполнении вызова
F(10)?

Демонстрационный вариант ЕГЭ 2017 г. – задание №11

Демонстрационный вариант ЕГЭ 2016 г. – задание №11

Ниже на пяти язы­ках про­грам­ми­ро­ва­ния за­пи­са­ны две ре­кур­сив­ные функ­ции (про­це­ду­ры): F и G.

Бейсик

DECLARE SUB F(n)
 DECLARE SUB G(n)
 
 SUB F(n)
    IF n > 0 THEN G(n - 1)
 END SUB
 
 SUB G(n)
    PRINT "*"
    IF n > 1 THEN F(n - 3)
 END SUB

Python

def F(n):
    if n > 0:
        G(n - 1)
def G(n):
    print("*")
    if n > 1:
        F(n - 3)

Алгоритмический язык

алг F(цел n)
нач
    если n > 0 то
        G(n - 1)
    все
кон
 
алг G(цел n)
нач
    вывод "*"
    если n > 1 то
        F(n - 3)
    все
кон

Паскаль

procedure F(n: integer); forward;
procedure G(n: integer); forward;
 
procedure F(n: integer);
begin
    if n > 0 then
        G(n - 1);
end;
 
procedure G(n: integer);
begin
    writeln('*');
    if n > 1 then
        F(n - 3);
end;

Си

void F(int n);
void G(int n);
 
void F(int n){
    if (n > 0)
        G(n - 1);
}
 
void G(int n){
    printf("*");
    if (n > 1)
        F(n - 3);
}

Сколь­ко сим­во­лов «звёздоч­ка» будет на­пе­ча­та­но на экра­не при вы­пол­не­нии вы­зо­ва F(11)?

def F(n):
    if n > 0:
        G(n - 1)
def G(n):
    print("*")
    if n > 1:
        F(n - 3)

Чему равно значение функции F(5)?

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) * (n + 2), при n > 1

Чему равно значение функции F(5)? В ответе запишите только целое число.

Сколь­ко сим­во­лов «звёздоч­ка» будет на­пе­ча­та­но на экра­не при вы­пол­не­нии вы­зо­ва F(5)?

Дан рекурсивный алгоритм:

Python

def F(n):
  if n > 0:
     print('*')
     F(n-2)
     F(n-1)
     F(n-1)
  print('*')

Паскаль

procedure F(n: integer);
begin
 if n > 0 then begin
    writeln('*');
    F(n-2);
    F(n-1);
    F(n-1);
 end;
 writeln('*');
end;

Си

void  F(int n)
{
 if (n > 0) {
    printf(″*″);
    F(n-2);
    F(n-1);
    F(n-1);
 }
 printf(″*″);
}

Сколь­ко сим­во­лов «звёздоч­ка» будет на­пе­ча­та­но на экра­не при вы­пол­не­нии вы­зо­ва F(5)?

Алгоритм вычисления значения функции F(w), где w — натуральное число, задан следующими соотношениями:

F(1) = 4; F(2) = 5;

F(w) = 4*F(w—l)- 3*F(w-2) при w > 2.

Чему равно значение функции F(8)?

Алгоритм вычисления значений функций F(w) и Q(w), где w — натуральное число, задан следующими соотношениями:

F(1) = 1; Q(1) = 1;

F(w) = F(w-1) + 2*Q(w-1) при w > 1

Q(w) = Q(w-1) — 2*F(w-1) при w > 1.

Чему равно значение функции F(5)+Q(5)?

Дан рекурсивный алгоритм:

def F(n):
    print('*')
    if n > 0:
        F(n-2)
        F(n // 2)
        F(n // 2)

Сколько символов «звездочка» будет напечатано на экране при выполнении вызова F(5)?

Дан рекурсивный алгоритм:

def F(n):
    print(n)
    if n < 7:
        F(n+3)
        F(n*2)

Найдите сумму чисел, которые будут выведены при вызове F(2).

Дан рекурсивный алгоритм:

def F(n):
    print(n)
    if n < 6:
        print(n)
        F(n+1)
        F(n+2)
        F(n*2)

Найдите сумму чисел, которые будут выведены при вызове F(1).

Дан рекурсивный алгоритм:

def F(n):
    if n > 3:
        return F(n - 1) * F(n - 2)
    else:
        return n

Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(6)?

Ниже записаны две рекурсивные процедуры, F и G:

def F(n):
    print('*')
    if n > 0:
        G(n - 1)
def G(n):
    print('*')
    if n > 1:
        F(n - 2)

Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(13)?