Chapter 3: Recursion

• every recursive function has two parts:

  • base case

  • recursive case

  ex:

  def countdown(i):
    print i
    if i <=0:  //Base case
      return
    else: //recursive case
      countdown(i-1)
  ​
  print(countdown(5))

• The call stack

  ​
  def factorial(num):
    if num ==1:
      return 1
    else:
      return num * factorial(num-1)
  ​
  print(factorial(4))

• Recap

  • Recursion is when a function calls itself.

  • Every recursive function has two cases: the base case and the recursive case.

  • A stack has two operations: push and pop.

  • All function calls go onto the call stack.

  • The call stack can get very large, which takes up a lot of memory.

• Stack

  • Push(Add a new item to the top)

  • Pop(remove the topmost item and read it)