Рекурсия

Суть в том что бы понять как работает рекурсия.

Тут собран набор простых и не очень задачь для того чтобы рекурсия перестала пугать твои неокрепшие програмисткие навыки.

Начнем с базы. Рекурсия похожа на цикл, или проще говоря у неё тоже есть момент когда она должна остановиться. Нечто похожее на цикл while или for или вообще на reduce из мира функционального программирования.

Что такое рекурсия? Рекурсия это самоподобие.

Для того чтобы закодить рекурсию обычно необходимо найти две вещи:

1. Граничный случай - рекурсия отработает и больше не будет выполнятся
2. Рекурсивный случай - рекурсия вызывает саму себя

Это необходимо чтобы не произошел “бесконечный цикл”

0

Закодить цикл for от N-1 до 0 (включительно) не используя ключевые слова while и for

def other_func(n):
    print(n)


for_from(5, other_func)

Вывод:

4
3
2
1
0

1

Закодить цикл for от 0 до N (0 <= N) не используя ключевые слова while и for

что то вот такое:

def other_func(n):
    print(n)

for_n(5, other_func)

вывод:

0
1
2
3
4

2

Классическая задача.

Суммирование. На вход подается массив. Нужно найти сумму. По прежнему цикл или функцию sum использовать низя.

Но можно использовать слайсы: arr[1:10]

sum_rec([1, 2, 3, 4, 5, 6])

3

Обход дерева.

{
    "name": "other string root",
    "children": [
        {
            "name": "other string 1",
            "children": []
        },
        {
            "name": "other string 2",
            "children": []
        },
    ]
}

Нужно пройтись по входяшему джсону или похожем объекте и вывести все имена.

Должен получиться такой вывод:

other string root
other string 1
other string 2

Примечание Для пустого массива детей рекурсию можно не вызывать

4

Обход дерева. Усложненный

{
    "tag": "root",
    "left_nodes": [
        {
            "name": 1,
            "left_nodes": [
                {
                    "name": 2,
                    "left_nodes": [],
                    "right_nodes": []
                }
            ],
            "right_nodes": [
                {
                    "tag": "puk",
                    "left_nodes": [],
                    "right_nodes": []
                },
            ]
        },
        {
            "name": 3,
            "left_nodes": [],
            "right_nodes": []
        },
    ],
    "right_nodes": [
        {
            "tag": "1",
            "children": []
        },
        {
            "tag": "2",
            "children": []
        },
    ]
}

Нужно пройтись по входяшему джсону или похожем объекте и вывести все имена.

Имя левых нод - "left node " + str(-name)
Имя правых нод - "right node tag:" + tag

Корневая нода - правая

Должен получиться такой вывод:

right node tag:root
left node -1
left node -2
right node tag:puk
left node -3
right node tag:1
right node tag:2

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1