Рекурсия с типами возврата

Question

Как понимать сложные рекурсии?Я просто нахожу примеры рекурсии начального уровня.Я хотел знать, как понимать рекурсию и стек вызовов, когда используется сложная логика.

 public Boolean recursion(int value, string name)
    {
        if (value > 10 && value<12)
            return false;

        if (value > 110)
            return false;

        if (value > 104 && value < 106)
            return false;
        return recursion(value+1,"left") || recursion(value+100,"right");
    }

или, если быть точным, следующая логика

 public bool HasPathSum(TreeNode root, int sum) {
 if (root == null)
    return false;
if (root.val == sum && (root.left == null && root.right == null))
    return true;

return HasPathSum(root.left, sum - root.val)
        || HasPathSum(root.right, sum - root.val);
}

Как я понимаю потокприведенный выше пример рекурсивной функции?

Answer 1

Рекурсия немного сложна, вам нужно отслеживать каждый раз, когда вызывается функция.При каждом вызове создается отдельный стек.

В частности, для второй функции она проверяет, равна ли сумма узловых путей к конечному листу определенному значению.Условие ИЛИ || существует, потому что путь может быть либо в левом, либо в правом поддереве - если кто-либо удовлетворяет его, sa true.

Строка if (root.val == sum && (root.left == null && root.right == null)) проверяет, что, пока вы не достигнете листа,sum равно value.Также обратите внимание, что value уменьшается и затем используется для рекурсивного вызова, потому что node рассматривается и его значение учитывается, остальные узлы от этого узла до листа должны иметь сумму меньше, чемисходная сумма (меньше по значению текущего узла).