Programming techniques (excluding OOP)

Made from P.M.T and Ada Comp. Sci. notes

Are for loops in pseudo code inclusive (e.g. for val = 0 to 5… will the code within loop execute when val=5)?

Yes, for loops are inclusive

What columns would a trace table have tracing a recursive algorithm?

• Function call

• Any parameters the recursive function has

• return

What is the DIV operation? Give an example

Integer division. For example 40 DIV 12 = 3 (26÷12= 3 remainder 4)

What is the MOD operation? Give an example

Modulo; the remainder of a division. For example, 40 MOD 12 = 4 (26÷12= 3 remainder 4)

What are the 3 programming constructs?

• Sequence

• Selection (aka branching)

• Iteration

What is the sequence programming structure also known as?

Branching

What is the sequence programming construct?

When code is executed line-by-line, from top to bottom

What is the selection programming construct?

A certain block of code is only run if a specific condition is met

What is the iteration programming construct?

Repeatedly executing the same block of code a number of times or while a condition is met

What is the difference between branching and iteration?

• Branching decides which code is run

• Iteration repeatedly runs the same code in the same sequence

What are the two types of iteration?

• Count controlled / definite iteration

• Condition controlled / indefinite iteration

Describe count-controlled iteration

• Code is repeated a specific number of times

• It is definite iteration

What loops use count controlled iteration?

For loops

Describe condition-controlled iteration

• The block of code is repeatedly run until a condition is met.

• The number of repetitions is not fixed - it is indefinite iteration

What types of loops use condition controlled iteration?

While, do while & repeat until loops

Define recursion

A programming construct in which a subroutine calls itself during its execution

What are the key features of a recursive algorithm?

• The function calls itself

• There is a base case / condition that stops the recursive calls

• Each recursive call will create a new copy of the values in the function and add all of the values of the copy the call is being made from to a stack 

• There may be more than one base case

Advantages of recursion

• Can represent certain problems with fewer lines of code, meaning that the function is:

  • Easier to read

  • Less prone to errors

• Natural way to process certain data structures (such as trees) that are recursive by nature

Disadvantage of recursion

• Harder to trace which makes debugging more difficult

• Uses more memory because of the need to store multiple stack frames. If the call stack runs out of memory, there will be a stack overflow, and the program will crash.

• Can be slower because of the need to manage stack operations.

What does passing a parameter by value mean?

• The subroutine receives a copy of the variable

• Changes are made to the copy

• Changes don’t overwrite the original value

• The copy is deleted/no longer available when the function ends

What does passing a parameter by reference mean?

The address of the parameter is given to the subroutine

Changes value of the parameter will be updated at the given address.

Are parameter(s) passed by value or by reference in recursive subroutines, and why?

• If the parameter is sent by value, it will be a copy of the parameter that is used so the parameter wont be overridden. This will produce the correct output.

• If the parameter is passed by reference it would not produce the correct result as it would be overridden / because it is a pointer to the address of the variable.