редица на Stern-Brocot

Числовата редица на Stern-Brocot (Stern-Brocot sequence, Stern's diatomic series, fusc(n) – последното е дадено от Dijkstra) съдържа естествени числа, представени чрез рекурентна формула: a(2*n) = a(n), a(2*n+1) = a(n) + a(n+1) за a(0) = 0, a(1) = 1. Всеки два съседни елемента на редицата са взаимно прости числа - най-големият им общ делител е 1. Редицата на Stern-Brocot е описана подробно в https://oeis.org/A002487. Начални елементи в редицата са: 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5 ...

Съставете програма, чрез която се въвежда естествено число N от интервала [1..25] и се извеждат посочения брой елементи от числовата редица на Stern-Brocot. Програмата да използва две аналогични функции - рекурсия и итерация.

Подробно описание за редица на Stern-Brocot може да намерите и на следните адреси: https://en.wikipedia.org/wiki/Stern–Brocot_tree; http://mathworld.wolfram.com/Stern-BrocotTree.html; https://rosettacode.org/wiki/Stern-Brocot_sequence.

Дървото на Stern-Brocot е балансирано двоично дърво, чийто върхове имат стойност отношение на две естествени числа. Чрез него е проектирана системи от зъбни колела (часовников механизъм) с предавателно число близко до желаната стойност.

Дървото на Calkin–Wilf е също балансирано двоично дърво, в чийто два върха, с общ родител, стойностите се определят от два съседни елемента от редицата на Stern-Brocot - числител на левия елемент и знаменател на десния елемент, другите две стойности са еднакви и са равни на сумата от същите два съседни елемента.

Разгледайте други основни типове примерни задачи, за чието решение се използват числови редици, както и редица на Farey, дърво на Calkin–Wilf, дърво на Stern-Brocot.