Тест по предмету «Информатика» на тему «Рекурсия»

1. Дана рекурсивная функция:

def F(n):
    if n == 0:
        return 1
    return n * F(n - 1)

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

2. Дана рекурсивная функция:

def f(n):
    if n < 10:
        return n
    return n % 10 + f(n // 10)

Что вернёт вызов f(2345)?

3. Числа Фибоначчи заданы рекурсивно: F(1) = 1, F(2) = 1, F(n) = F(n - 1) + F(n - 2) при n > 2. Сколько всего вызовов функции F, включая первоначальный, произойдёт при вычислении F(4) без мемоизации?

4. Дана рекурсивная функция:

def g(n):
    if n == 0:
        return 0
    return g(n - 1) + 2 * n

Чему равно значение g(3)?

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

Ответы

1. 120
2. 14
3. 5 вызовов
4. 12
5. Если n < 10 (число однозначное), вернуть n.