β quick recursion question
I have a tests about lists and recursion next friday and I'm really worried because these are easily the 2 subjects I'm the worst at from what we've learned so far. we got a bunch of assignments to turn in until sunday night to practice but I find them really hard. I managed to do most of them but it took a lot of trial and error which I can't do during a test.
the final question in one of assignments is to write a recursive function that gets a list of int and returns whether it is descending or not, meaning if each node is smaller than the node that came before it. for example:
list -> 3 -> 2 -> 1 -> null is descending
list -> 2 -> 3 -> 1 -> null is not descending
I need to practice so don't tell me the code but broadly how to do it? I have no idea honestly
3 Replies
How would you check if a list of ints is in a descending order or not using a simple
for or while loop?When dealing with recursion, you need two things:
- A base case.
- A way to reduce a more complex case down to a less complex case.
So for example, if the question is "how to prove 42 is an even number" then you can have:
- Base case: 0 is an even number.
- Reduction: n is an even number if n-2 is an even number.
So starting with "42 is an even number if 40 is an even number" and then "40 is [...] if 38 is [...]" and repeat all the way until you reduce it down to the base case 0.
Try to think up a base case and a reduction that would work for your original question.
omg people I got it tyyyyyy