Be warned, this may take some time to sink in. But there are many problems that fit this pattern, and once used to this way of thinking (takes even more time) it is actually very simple and powerful.
We are going to write a function
flatten that flattens an arbitrarily deeply nested list.
This means that when the function is done, it can use itself.
Therefore, when iterating through a nested list, we can use
flatten to flatten it, and add that flat list to our result. Non-list values are added to the result without modification:
result = 
loop through lst
if the element is a list, flatten(elem) and put the values in result
otherwise the element is non-list and should be added as-is
What will happen is that each time it encounters a list, it will call itself with that list as the argument. That argument will have 1 less nesting level. Which means that eventually we come to the situation where we have an already flat list. If we look at the code above we see that such a list would simply be copied and our function returns. Because it returned, it will allow the previous call to return as well because it flattened all its lists. Which in turn allows the previous to finish and so on, until the whole list is flat.
So in general:
1) Split up the problem into less complex problems. They must eventually reach a trivial case.
2) Assemble the results to solve the current problem.
3) Make sure that the trivial cases are solved without recursion.
How the above corresponds to flatten:
1) Call flatten for each sub-list, which will each be 1 depth less
2) Add each value to result after flattening / add non-list values to result
3) A flat list gets copied and then returned, which then allows the rest to be solved.
Some more help in getting this to sink in:
Read the above code. Just assume that the
flatten call will do what it's supposed to without considering why it does.
Convince yourself of that with that assumption, the correct result will be produced.
Convince yourself of that the depth of the lists is reduced by 1 every time
flatten is called, and that this eventually leads to flat lists only.
Convince yourself of that flat lists cause
flatten to return without recursion.
Convince yourself of that every time
flatten runs, everything is split up into simpler problems that will eventually be solved, the problem will never grow, it will only shrink, and never get stuck, therefore the whole thing will get solved.