leetcode-recursive-function

a few things to guide recursive

tags: learning programming leetcode

content

a few things to guide writing recursive functions

1. base case
   • the base case determines when the function stops
   • more importantly, it determines what the sub-problem returns!
2. it’s about breaking down problems to sub-problems
   • if there’s still a sub-problem, call itself (the recursive function)
3. previous state, current state, next state as function input arguments
   • keeping track of the state of the sub-problems
   • this is how you shrink the problems
4. remember to return back to the call stack (and the original caller of the recursive function), not just the base case
   • think “what is the calling function waiting to be returned?”

regarding the last point:

• i wrote something like

def my_recursive(curr, prev) -> something:
 if curr is None:
  return prev
 # do something
 my_recursive(curr.next, curr)

• took me a while to figure out what’s wrong
  • it should be return my_recursive(curr.next, curr)
  • otherwise, there’s no return other than the base case
  • if it’s Go, compiler is gonna complain about no return
  • but it’s python, None is implicitly return when there’s no return case

up

down

reference