Максимальная сумма дерева в схеме

Question

У меня проблемы с упражнением, которое я пытаюсь выполнить, потому что я новичок в этом языке, и рекурсивное мышление для меня довольно сложно.У меня есть дерево (не обязательное двоичное), и мне нужно найти путь, который дает максимальную сумму.Например, у меня есть дерево: '(1 ((0) (2 ((3) (2))) (5))), указанное на изображении

Дерево примера

        1
  0     2     5
      3   2

Так что я должен сделать функцию: (function '(1 ((0) (2 ((3) (2))) (5)))) и он должен вернуть 6 (в этом случае).Есть 2 пути, которые дают ответ: 1 + 2 + 3 = 6 и 1 + 5 = 6. Я пытался «перевести» код на python , найденный здесь , но я понятия не имею, как это сделатьэто рекурсивно в Схеме.

Answer 1

Рекурсия довольно проста, вам просто нужно проверить 3 случая:

NUMBER?
NULL?
PAIR?

Таким образом, в схеме вы бы структурировали ее так:

(define (tree-sum t)
  (cond ((number? t)
         ...)
        ((null? t)
         ...)
        ((pair? t)
         ...)))

pair? oneэто рекурсивный случай, в котором вы складываете суммы car и cdr.Надеюсь, это поможет!