Recursion:
X Equals Change X

University of Washington (Practice-It) Slides on X = Change(X) Recursive Pattern

There are a certain class of recursion problems that follow a familiar x = change(x) pattern. This pattern is often used to manipulate trees.

Here are the slides (created by Marty Stepp) for the x = change(x) recursion pattern: 

https://drive.google.com/file/d/1JpS4BqKO9hINWF9eNedB7spi2lbmE0GA/view?usp=drive_link

Practice Problems for X = Change(X)

Once you have gone over the slides, above, for the x = change(x) pattern, you can practice the pattern by doing the following problems on Code-Step-By-Step:

Important Notes: It is especially important that you complete the above exercises in the order given. The problems that do not require
the X = change(X) pattern are much easier, and, as such, should be completed first.

BJP5 Chapter 17 

• Exercise 18: inOrderList
  
  This problem does not require the X = change(X) pattern. It requires you to write a variation of the inorder parsing algorithm you wrote previously for binary tree parsing. However, instead of printing the node values as you encounter them, you are asked to insert the elements into a list as they are visited. The list can be passed as a parameter to the recursive helper. The recursive helper can add elements to this list without needing to use the X = change(X) pattern.
  
  
  

• Exercise 20: makePerfect
  
  This exercise does not require the use of the X = change(X) pattern. It is slightly harder than the completeToLevel problem that follows next. It is listed ahead of that problem because your instructor will likely do this problem for you in class and then ask you to do the completeToLevel problem on your own. The two problems are extremely similar.
  
  
  

• Exercise 14: completeToLevel
  
  This exercise also does not require the use of the X = change(X) pattern. However, this problem (as well as the makePerfect problem) uses non-tail recursion. As such, both are academically challenging.
  
  
  

• Exercise 16: tighten
  
  This is the first of the exercises in this section that requires the X = change(X) pattern.
  
  
  

• Exercise 19: evenLevels
  
  This exercise requires the X = change(X) pattern.
  
  

• Challenge Problem: combineWith