Recursive functions are ones that call themselves. We watched a video in class to better understand the phenomenon.
Download the code scaffold and write recursive definitions for each function. Add
@return lines to the comments for each function definition. (This weird-looking comment style is designed to work with tools that generate documentation automatically. As painful as it is to comment your code, it's much easier to do it as you write it rather than to try to come back and write all the comments later. You'll wish you had never been born.) The supplied
main() function will test your code. Definitions that aren't recursive receive no credit. Submit your file
recursion.cpp when you are finished.
Need something else to try?
Rewrite problem 3 from homework 3 (the diamond problem) so that the diamond is drawn via two recursive functions, one that draws the top half and one that draws the bottom half. What other recursive pictures can you code up?
Tips on recursive programming
It can be hard to understand how to write a recursive function. Here are some tips.
- Resist the temptation to loop. While there's nothing stopping a recursive function from containing
for loops, such simple functions as we are writing today don't need them. Since your brain is used to thinking in loops, try to avoid it entirely while we are trying to think recursively.
- Handle the common case first. This is the case that happens "most of the time". Usually, it's at home in an
else clause connected to some
if...else if statements that check for the base case.
- Make sure your base cases make sense, and will always occur. The action of the common case should (at each recursive step) get you closer to the base case. If your conditions are malformed, you will end up in an infinite loop.
- Don't be afraid to hand-trace, and "when in doubt,
- Don't be afraid of a very silly base case! Very often, base cases are things that seem trivial. You can make it work.
- To beginners, recursion seems like magic. Make an effort to write these functions today and you will appreciate the new understanding you obtain.