##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Time and space breakdown
Each recursive call reduces by half (when even) or by (when odd). In the worst case, you halve about times before reaching .
Time complexity: . You make at most recursive calls, and each call does work (one multiplication).
Space complexity: for the recursion stack. You can convert this to an iterative solution to reduce space to , but the time stays .
