Many recursive solutions to problems of size N follow the pattern:
Step 1: Solve the problem for the smallest input (say, n = 1)
Step 2: Given the solution to the same problem of size n = k-1 (k <= N), solve it for n = k.
We can see the inductive nature of this, which is why we typically use induction to prove recursive algorithms. For some problems, like recursive Fibonacci, this pattern emerges in an obvious way. My question is if, say, Binary Tree Traversal can be seen as also following this pattern?
Take Depth First Search for instance:
def DFS(root):
if root == None:
return
print(root.value)
DFS(root.left)
DFS(root.right)
I understand the code and the call stack, but I'm struggling to articulate exactly what the steps 1 and 2 are for DFS (in holding with the structure of recursive solutions outlined above). It can't be that the only base case is when the current node is None, because traversing a single node should also be a base case.
If I say that line 4, the one containing the print statement, is a base case it wouldn't make much sense because it runs for every sub-tree.
It follows the same pattern.
The "problem" to solve is printing the tree in the right order. Your code implements pre-order.
Step 1: Solve the problem for the smallest input (say, n = 1)
The smallest problem here is printing an empty tree (root is None). In that case the solution is to print nothing (just return).
Step 2: Given the solution to the same problem of size n = k-1 (k <= N), solve it for n = k.
We can consider k to represent the number of nodes in the current tree, and n to be the number of nodes in a direct subtree of this tree. Printing the left or right subtree is a smaller problem, where n <= k-1 (note the <=).
Printing the tree (in pre-order), consists of printing the root node, and then solving the "problem" for the left and right subtree.
One difference is that the output of the tree is a "side-effect" of this function -- it does not return the result, but outputs it. That means that the one making the recursive call does not need to get back a result to work with. A more pure function would return a string representation of the tree, and the caller would use that in a concatenation with the string it is building, and which it will return to its own caller.