SC recursion

• R14: recursion
  • decompostion
  • structure of recursive implementations
  • choosing the right recursive subproblem
  • recursive problems vs. recursive data
  • Mutual recursion
  • reentrant code
  • when to use recursion rather than iteration
  • common mistakes in recursive implementations

R14: recursion¶

有时候会觉得自己对recursion/iteration的了解已经够多了，但不够多总是常态。尤其在应用到不同的场景的时候。

decompostion¶

Choose the right decomposition for a problem.

recursion is one method

structure of recursive implementations¶

helper methods: don’t expose the helper method to your clients.

base case + recursive case

choosing the right recursive subproblem¶

Think about several ways to break down the problem, and try to write the recursive steps.

Recursive subproblem can be smaller or simpler in more subtle ways.

recursive problems vs. recursive data¶

• recursive problems

• recursive data

  • file systems
  • data structures: binary search tree

Mutual recursion¶

return immutable object

reentrant code¶

• it can be called again even while a call to it is underway.
• many application scenario: concurrency, callbacks, mutual recursion…

when to use recursion rather than iteration¶

像递归这样只用考虑输入和输出模式的范式属于函数式编程的一种。它与命令式编程/迭代还有一个主要区别就是可变性(mutablity)，不可避免产生的可变变量在迭代过程中不断改变，导致出现漏洞。但递归相较于迭代的明显的缺点就是需要更多的空间。

building up a stack of recursive calls consumes memory temporarily, and the stack is limited in seze.

common mistakes in recursive implementations¶

• base case missing
• recursive step fails to reduce to a smaller subproblem
• aliases to mutable data structures are inadvertently shared, mutated among the recursive calls.

Bright side: fail faster. StackOverflowError.