(Sequence, Selection), Iteration and Recursion – AS Computing Revision (F452)

The Three Basic Constructs

  • Sequence – All instructions are carried out, once, in the order they appear
  • Selection – There is a logical condition, which determines which, if any, of the statements will be executed
  • Iteration – There is a logical condition, which determines how many times, if any, the statements will be executed (in other words, a group of statements are repeated whilst or until a condition is met)
  • (To see how to write various constructs in Java, please see my pseudocode post
  • (I’m going to assume you know how to use sequence and selection)

Types of Iteration

  • There are three types of iteration you could come across in the exam, but they all have things in common
  • Once the bottom of the loop is reached, the computer jumps back up to the top and does it again… or not, depending on the condition
  • The condition is tested each time ’round
  • The loop body has to change some element of the condition expression, or the loop will be infinite
  • The condition has to be initialized somehow
Type Location of Condition True or False? Notes
WHILE Top of loop Continues whilst condition is true / until condition is false Code may not even be executed once
REPEAT Bottom of loop Continues whilst condition is false / until condition is true Code will always be executed at least once
FOR Top of loop Counts through the values you specify For counting only – increments and initializes automatically

Converting Between Loop Types

  • The most foolproof way to convert between different types of iteration is to work out exactly what the loop you’re converting does, and then write a new loop that does the same thing, completely from scratch, using a different type of iteration
  • Here are some tips, though:
  • When converting a WHILE counting loop to a REPEAT counting loop, or vice versa, reverse the direction of the inequality sign in the condition, and add an “or equal to” if there isn’t one / remove the “or equal to” if there is one
  • When converting from WHILE or REPEAT counting loops to FOR loops, locate the initialization and the finishing number – transfer those into the FOR loop. FOR loops include the starting and finishing numbers, so if you’re converting from a WHILE loop that doesn’t have an “or equal to”, the FOR will count one number too far – compensate for this by decreasing the destination number by 1 (or increasing it by 1, if your loop counts backwards)
  • When converting FOR to WHILE or REPEAT, find the initializer and end number, and transfer those. The initialization will have to be done just outside (before) the loop. Replace the FOR’s NEXT with a proper incrementation statement, and remember to put an “or equal to” on the WHILE’s condition (if it’s a REPEAT, that’s unneccessary)
  • (No, you don’t type “or equal to”! You put a = after the > or <)

Recursion

The execution of this C function: void func(in...

The execution of this C function: void func(int num){ if(num func(num+1); printf(“%d\n”, num); } } (Photo credit: Wikipedia)

  • It’s not a construct, as such, but it’s an alternative to iteration that you’ll need to know about
  • A function is a procedure that returns a single value (I’ll probably create a post explaining procedures and functions in detail)
  • A recursive function (or procedure, I suppose) calls itself… within itself…
  • When you count with it, it kinda works backwards
  • Like iteration, recursion must be initialized, a condition must be tested, and something must change so that the condition eventually works out differently, and it can stop
  • To understand what’s going on, you need diagrams with arrows showing each call and return
  • The stopping condition in recursion is usually an IF statement that’ll call the function again under a certain condition, or otherwise return and end the whole mess

Recursion VS Iteration

  • Iteration is faster than recursion
  • Iteration uses a fixed amount of memory,
  • You could argue that it simplifies big problems by dividing them into small steps
  • Apparently, humans often naturally describe how to do things in a recursive way (I don’t – I describe things in an iterative way, actually!)
  • The exam board thinks recursion is easier to understand and maintain, leading to simpler algorithms that are easy to trace through
  • Multiple versions of the process are held in memory at the same time, which means it might run out of memory and crash
Advertisements

About Matt

I like writing, filmmaking, programming and gaming, and prefer creating media to consuming it. On the topic of consumption, I'm also a big fan of eating.
This entry was posted in AS Computing Revision, Revision and tagged , , , , , , , , , , , , , , , . Bookmark the permalink.

Enter comment:

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s