>>14278545First, recursive functions are the right tool to manipulate recursive data structures (lists can be viewed as recursive DSC, trees, ..)
Recursive functions are made of a conditional at the top level of the function, at least 1 base case, at least 1 recursive case.
You can have several base cases, several recursive cases, and an arbitrary nesting of the conditionals.
Now, the things to look for (probably incomplete) :
- how many recursive call is there ?
--> one (ex: iterating over a list)
--> multiples :
----> reduction of input :
------> minus 1 (ex: iterating over a list, factorial)
------> divided by 2 (ex: walking over a tree (pre-, in-, post-order traversal)
----> overalapping ? :
------> no (ex: walking over a tree)
------> yes (ex: factorial)
- is the recursive call in a tail recursive position ?
(is the recursive call returning directly or do we apply an operation on its result ?)
- is there an accumulator ? can it be refactored using an accumulator ?
=> why ? as to make the function tail recursive and not blow up the stack
-> accumulator adds an extra argument, so generally we use a helper function
- what information does the stack contains ?
- or what information does it encode ? (ex: can be that 1 stack frame encoded for the number 1 in a recursive implentation of the additiion function. can be that the stack corresponds to the path in the tree that is walked over)
