Programming techniques (excluding OOP)

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

A for loops in psuedo 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?

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

What is the MOD operation?

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 construct?

What is the sequence programming construct?

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 a block of code a number of times or while a condition is met

Count-controlled iteration

• Code is repeated a specific number of times

• Definit iteration

• Uses for loops

Condition-controlled iteration

• Repeitions are based on if a condition is met or not.

• Indefinite iteration

• Uses 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 debuging 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.

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.