recursive-function-starting-case

starting case of recursive functions

tags: learning programming leetcode

content

• we always think about base case of a recursive function

• we should think about its starting case too

  • i.e., the first ever function call

• look at the recursive call for merging linked list:

def recursive(list1, list2) -> LinkedList:
	if not list1 or not list2:
		return list1 or list2
	
	if list1.val < list2.val:
		list1.next = recursive(list1.next, list2)
		return list1
	else:
		list2.next = recursive(list1, list2.next)
		return list2

• i got confused by why return list1
• return list1 because:
  • in the first ever call to recursive, list1/list2 is the head of the lists
  • this is the original problem, not the broken down sub-problems
    • this is the most outside (or bottom) of the function call stack to recursive
  • therefore, we could just return list1/list2 to the original caller of recursive

up

• leetcode-recursive-function

down

reference