I imagine recursion as walking down the sidewalk – at each square, you prepare something, and then when you get to the end, you turn around and walk back, picking up the something you prepared in each square. For this post, I'm going to be referencing the bunnyEars puzzle presented by Parlante on codingbat.
I often start writing my recursions by starting with the base case. Shaffer (2013) says the base case is an input that can be handled without needing to call the recursion. I think of it more as the end or final step. “What causes me to turn around, and what happens as I turn around?” For the bunnies, I turn around at bunny 0 and return 2 (the number of ears for a single bunny). Next, I add the code that changes with each step: bunny count subtract 1. After I subtract 1, I need to +2... but to where? This is the part that I have to always think about when writing these things. I add 2 to the recursion call.
For my sidewalk analogy, I come across a bunny. I scare it away and it leaves it’s two ears on the ground for me to pick up latter (don’t think about it too literally). I walk up to the next bunny and scare it away, it also leaves 2 ears behind. I keep going until I have scared all the bunnies. No bunnies means 0 ears at this step. Then I turn around and walk back the way I came picking up the ears.
I often start writing my recursions by starting with the base case. Shaffer (2013) says the base case is an input that can be handled without needing to call the recursion. I think of it more as the end or final step. “What causes me to turn around, and what happens as I turn around?” For the bunnies, I turn around at bunny 0 and return 2 (the number of ears for a single bunny). Next, I add the code that changes with each step: bunny count subtract 1. After I subtract 1, I need to +2... but to where? This is the part that I have to always think about when writing these things. I add 2 to the recursion call.
For my sidewalk analogy, I come across a bunny. I scare it away and it leaves it’s two ears on the ground for me to pick up latter (don’t think about it too literally). I walk up to the next bunny and scare it away, it also leaves 2 ears behind. I keep going until I have scared all the bunnies. No bunnies means 0 ears at this step. Then I turn around and walk back the way I came picking up the ears.
public int bunnyEars(int bunnies) {if (bunnies == 0) { // no more bunnies// recursion endsreturn 0; // no bunnies, no ears. Return “turns me back around”} else {// recursion needed,bunnies --; // scare away a bunnyreturn bunnyEars(bunnies) +2 ; // trigger recursion- walk further down, the bunny at this level “left behind” 2 ears.}}
Factorials are not my strong suit; I’ve never done well with them before. After writing up how I visualized and processed the bunny ear example, I got the factorial right for the first time:
public int factorial(int n) {if (n <= 1) { // 1 is the lowest n is allowed to goreturn 1; // return 1 so it can be multiplied by the previous layers n} else {return factorial(n-1) * n; // each turn, reduce n by 1, when walking back, multiplied by that level's n}}
Puzzles from: Parlante, N. (2016). Recursion-1. Retrieved from http://codingbat.com/java/Recursion-1
Shaffer, C. A. (2013). Data structures and algorithm analysis. (Edition 3.2). Retrieved from http://people.cs.vt.edu/~shaffer/Book/JAVA3elatest.pdf
Ps: I did have several iterations of the bunny problem that all worked. More than one way to code a rabbit:
No comments:
Post a Comment