Chapter19.2: Recursion

Posted on Edited on In , Views: Disqus:

Essential features of recursion:

  • It is defined in terms of itself // it calls itself
  • It has a stopping condition
  • It has self-contained subroutine
  • It can return data to its previous call
  • --
  • Must have a base case/ stopping condition
  • Must have a general case
  • … which calls itself recursively // defined in terms of itself
  • … which changes its state and moves towards the base case
  • Unwinding occurs once the base case is reached

Explain a reason why a stack is a suitable abstract data type(ADT) to implement recursion:

  • A stack is a LIFO(last in first out) data structure
  • Each recursive call is pushed to the stack
  • And is popped when the function ends
  • Enable unwinding/back tracking
  • … to maintain the required order

What a compiler has to do to translate recursive programming code

  • When the recursive call is made, all values/data are put on
  • … the stack
  • When the stopping condition/base case is met
  • … the algorithm unwinds
  • … the last sets of values are taken off the stack (in reverse order)