Recursion is required when one wants to traverse a tree-like structure.
the tree structure can be a real tree, based on tree-like data like a parent-child list, or sn imagined tree, like calculated by an algorithm.a tree traversal structure could be limited by:
- Repetitions in each node: algorithm-based (calculated) repetitions, or based on data of possible child nodes of a node or few static function calls that are like nodes.
- a rule when it is the end of all nodes, Like there are no sub-branches left.
Because recursion is done to get a result. so usually to store the result, need away to store the result:
- a pointer data type (a reference) parameters are used, Like an object or a list is used (passing references is a replacement for a global variables. it acts like a proxy for a variable elsewhere).
- also, one can use a global variable
- or accumulating parameters and to return a value.
- these are used to return the calculated result.
- however rarely there is an operation that is done on each node and then there is no need to return a result.
recursion is like multi-branched loops.
each time before a new function is started, current function execution position and its variables are left on the “stack”, and the new function is appended to the stack. after the sub-function call ends, the before function resumes operation at the saved position, and with saved variables ( also the function is removed from the stack, and its return value is returned ).
a function that calls itself with only one branch each time is essentially a loop, like a for loop, or a while loop.
the return values of all sub-branches are available in parent loop.
in a recursion-function, we decide do we have more branches or not.
when starting a new recursion, the position of the branch for the new call is updated ( new sub-position is selected )
def countdown(n): if n <= 0: # do we dont have branches anymore? print('Blastoff!') else: # or we have some branches - print(n) countdown(n-1) # only one branch it is like a loop
It is worth noticing the function is executed from top to bottom. You will see that (in code below) append and pop executed before code in function and after the code in the function.
let’s accumulate the positions of branches:
def countdown(n, accumulated_results, backlog): backlog.append(n) print( "step", backlog) accumulated_results.append(backlog.copy()) # if .copy() does not work (need python version >3.3) # use backlog[:] if n <= 0: # do we dont have branches anymore? # (do we home more branches rule ) , it decideds based on # given state from previous function if to continue or not print('Blastoff!') else:# or we have some branches - print(n) # the n-1 argument is the sub-branch position information, # we were at n, now in the sub-branch, we will be at n-1 # for the (do we home more branches) rule to know. countdown(n-1,accumulated_results, backlog) # only one branch it # is like a loop, # result variables # are passed on as is backlog.pop() # from list, take the last item and remove it temp_backlog= # this variable it is temporary for the being of the recursion results= #these are like global variables that are passed by reference instead of being global countdown(3,results, temp_backlog) print ("all collected", results)
# it is possible to use default values for parameters to not pass temporary variables and even with same trick make the first level return a value, but this is out of the scope of this explanation.
def countdown(n, accumulated_results=, backlog=,toplevel=True): ... countdown(3)