Recursive Function Correctness

• Contract： It is the function the son function realized, the father function rely on, and realized for the grandfather.It is so-called faith leap. But I prefer 'Contract', when you write a recursive function, figure out its function is the first and most important step. Then your job is to

  • cover all of the boundary conditions, how to judge a boundary condition with arguments, what to return

  • if the son-function is right, how can this father function you are writing meet the contract for the grandfather function.

This seems complex and confusing, but actually sample: mathematical induction

base step: the boundary conditions. Its correctness is guaranteed by our special check one by one

induction step: if the son fucntion is right, we can make the father function right

requirement to use recursive function:

the function of recursive function can be achieved by tearing the question to same question only with smaller scole

E.G.

110. 平衡二叉树 - 力扣（LeetCode）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    # actually is getHeight and examine if is balanced
    def getHeight(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        left = self.getHeight(root.left)
        right = self.getHeight(root.right)
        if left == -1 or right == -1:
            return -1
        if abs(left - right) > 1:
            return -1
        return max(left, right) + 1

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        h = self.getHeight(root)
        if h == -1:
            return False
        return True
        

• getHeight will return the height of root if the tree is balanced, but if the root is not balanced, getHeight will return -1.

• the boundary condition: Null

• we assume the son function is right, and think how to make father function meets the contract:return the height of root if the tree is balanced, but if the root is not balanced, getHeight will return -1.

• then we get the correct answer of height of a tree and if it is balanced

using a special value -1 maybe confusing, so we can use a tuple (balanced: bool, height: int)