The Student Room Group

A Level Computer Science Recursion - help pls.

I've always struggled with wrapping my head around recursion, or at least following along with recursive algorithms. I sort of understand the whole idea of items being put into a stack and popping off once you're at the base case or whatever, but in theory i struggle, i find myself losing my place in the code or not knowing where the 3rd or 4th call lead back to once i pop something off. The question im stuck on is attached below, in simple recursion questions i am able to do it but this one is pretty complex and i'm struggling. if anyone can explain it simply i would appreciate it greatly.recursion1.pngrecursion2.png
Sorry you've not had any responses about this. :frown: Are you sure you've posted in the right place? :smile: Here's a link to our subject forum which should help get you more responses if you post there. :redface:
Original post by tShephard
I've always struggled with wrapping my head around recursion, or at least following along with recursive algorithms. I sort of understand the whole idea of items being put into a stack and popping off once you're at the base case or whatever, but in theory i struggle, i find myself losing my place in the code or not knowing where the 3rd or 4th call lead back to once i pop something off. The question im stuck on is attached below, in simple recursion questions i am able to do it but this one is pretty complex and i'm struggling. if anyone can explain it simply i would appreciate it greatly.recursion1.pngrecursion2.png

Hi! I'm a student ambassador at Strathclyde, as well as a fourth year software engineering student.

Merge sort is definitely one of the more complex sorting algorithms, so you shouldn't be worried that it isn't easy to understand. It's perfectly normal for it to take a lot of thinking to understand it, especially as it is so commonly recursive. The main idea behind a merge sort is:

1. Run through the entire list to be sorted
2. If there are multiple elements in the list to be sorted
2. a) Split the list to be sorted in half into two smaller lists (commonly called a "divide and conquer" algorithm)
2. b) Sort these two lists
2. c) Merge the two sorted lists
3. If there is only one element in the list to be sorted, return that one element (as logically a list of size 1 is already sorted)

The "merge" function (mentioned in step 2. c) is not particularly relevant to the question, as long as you understand that it is a function that runs through two sorted lists and returns one ordered list combining both of their elements. however, for completeness, the function works by:

1. Creating a new "combined list" to eventually return
2. While both of the sorted lists to be combined have elements in them
2. a) if the first element of the first list is smaller than the first element of the second list, add the bigger element to the "combined list" and remove it from the second list
2. b) if the first element of the second list is smaller than the first element of the first list, add the bigger element to the "combined list" and remove it from the first list
3. (reaching this point means either the first or second list are now empty) If there are elements left over in the first list, add them to the "combined list"
4. If there are elements left over in the second list, add them to the "combined list" (only step 3 OR step 4 is possible, not both)
5. Return the combined list

Looking at the "electronic answer document", you are to document which array (if any) is returned at different calls of the "mergeSort" function, the variable "S" (the starting point of the lists currently being worked on), "E" (the ending point of the lists currently being worked on) and "M" (the middle point of S and E, where the lists are split to be sorted). Knowing all of these things that need to be returned, you can see this is really just a wordier version of the simple problems you said you know you can do. The break point of the function is when there is only one element in a list to be sorted, the other variables are all simple enough when you know what the algorithm is trying to do. In my opinion, the best way to work this out for yourself in an exam situation would be drawing the list as a tree diagram, wherein you can see every level of split list (and from there can see which arrays are returned, and what "S", "E" and "M" must be at every stage). I suggest you have a look at "geeksforgeeks" (https://www.geeksforgeeks.org/merge-sort/) as they demonstrate this kind of working. They are very good for algorithms in general.

I hope this has given you some help as to how best run through this situation. If you can do the simpler ones, you will be able to do these examples with a bit of practice. You just need to not panic when you see longer examples like this, and break the problem down into terms you understand.

If you need any clarification with what I've written, please feel free to reply. You have all of the right ideas, if you can take your time and understand these examples you'll be ready for whatever comes up in your exam.

Cameron
Student Ambassador/Software Engineering Student

Quick Reply

Latest