Thread replies: 5
Thread images: 2
Thread images: 2
File: 1500355227884.jpg (244KB, 1485x1680px) Image search:
[Google]
244KB, 1485x1680px
So, in my CS class we're working with Recursion. We were given 4 basic rules:
1. Base Case: You must always have a base case.
2. Making progress: Recursive calls must be simpler instances of the problem
3. Design Rule: Assume Recursive calls work
4. Compound Interest Rule: Never duplicate work by solving the same instances of the problem multiple times.
I don't really understand the 3rd and 4th rules much, could anyone give a better understanding of them?
Also, a little extra question, how do I go about rewritting an expression to another expression of the form 2^f(n)? For example, 1024 * 2^n be rewritten to the form 2^f(n)? Appreciate any help on either of these.
>>
>>372612
Is this data structures? I haven't read the textbook yet desu
>>
>>372622
Yep, Data Structures.
>>
>>372612
These are rules on making recursive functions, I assume. Let's use merge sort as an example.
1) The base case is one item, which is sorted by definition.
2) When you recurse, you're operating on 2 lists with half the size. The size always goes toward 1.
3) When you call merge sort on the left and right halves of a list, and you are creating the code for after the recursive calls return, remember that by definition, those two halves are sorted. This may seem obvious, but some people get confused trying to understand what's going on. It's kind of like a time loop in a movie. This rule (and rule 4) drive your method for constructing the actual solution - in this case, it means you can step through the two halves of the list in linear time to combine them into one. You should be able to articulate how to construct a combined solution given partial solutions, if your procedure actually makes sense to do recursively.
4) This one seems self-explanatory. For merge sort, it means we would never have overlapping lists. A call that operated on indices 0-5 and 5-9, for instance, is performing extra work because index 5 is included in both lists.
As for your second question, I think you can log (base 2) both sides to solve for f(n).
log_2(2^f(n)) = f(n).
log_2(1024*2^n) = log_2(1024) + log_2(2^n) = 10 + n.
I'm sure it gets trickier for other expressions, but that's the idea.
>>
File: IMG_1331.jpg (44KB, 620x346px) Image search:
[Google]
44KB, 620x346px
>>372635
Ah, I understand now. Thanks anon, you saved my bacon.
Thread posts: 5
Thread images: 2
Thread images: 2