Какова связь между рекурсией и доказательством по индукции?

Какова связь между рекурсией и доказательством по индукции?

Допустим, fn(n),

рекурсия fn(n)вызывает себя до тех пор, пока не будет выполнено базовое условие;

индукция - это когда базовое условиевыполняется, попробуйте доказать (базовый случай + 1)также верно.

Кажется, что рекурсия и индукция идут в разных направлениях. Один начинается с nдо базового случая, другой начинается с базового случаядо бесконечного.

Кто-нибудь может подробно объяснить идею?