A question for the pros here, if you want to answer.
When you're dealing with recursive functions, do you imagine the whole tree of functions, or closely keep track on which step you are mentally? Or do you just summarize what is supposed to do and call it a day?
Like for:
Python:
def f(n):
if n <= 1:
return n
return f(n - 1) + f(n - 2)
print(f(8))
This one is simple, but would you imagine or picture in your head the whole tree/paths?
It's often convenient that you have the option to just think of it in terms of "what is this function doing on this immediate little subset of the problem".
So if you're processing a tree structure recursively, most of the time you spend coding, you can spend ignoring the big picture and just think about the specific little node you're working on in the immediate.
But in the back of your mind, you do need to remember that all recursive functions must have some base case where they finish their work, don't recurse, and return to trace the results back up the call stack.
The base case is usually easy enough and I can tack it to the front of function and the more elaborate meat of the logic is towards the end.
Here's a specific example from my little side project I've been working on for months.
The project involved a daemon that ran tasks that operate on streaming media sinks and sources. The daemon took as input a config file that specified those tasks, sinks and sources. But some sinks+sources can have multiple channels, so you can rewrite your config file to specify multiple tasks (that run in parallel).
But this was a simple enough scenario that I wondered, when you've got one task with a two-channel sink and a two-channel source, why can't the daemon detect and parallelize those itself? Maybe it could have some sort of command line option that would expand a naive config file into a more efficient one?
So I wanted to write a function that optimized a config. This is naturally a good fit for recursion, I think, because it involves tracing down a parse tree and possibly returning modified nodes.
The optimize function roughly would look like:
Code:
let rec optimize input =
let optimize_step input =
failwith "todo finish optimize step"
in
let output = optimize_step input in
if output = input
then output
else optimize output
So the internal function,
optimize_step, only expands one set of task+source+sink entries in one go. The reason I did this is because
optimize_step will need to add in additional checks in the final tree it generates, to avoid two task/source/sink names accidentally colliding in the final tree.
So the overall optimize function recursively expands step by step, until
optimize_step fails to find something new to expand, and just return its input unmolested. That's the base case.
If the
optimize_step output is the same as its input, then we're done and we can return it. Otherwise, recurse and expand another step.
Most of my thinking while writing
optimize_step can indeed focus just on the one case it's dealing with to the exclusion of everything else. Assuming that I write the base case properly.
