Recursion

Data in a computer program needs to be sorted.

Describe the steps a bubble sort will take to sort items into ascending order.

Darcie and Felix have both written a program that will perform a bubble sort to put these numbers into ascending order.

Darcie’s version will complete six passes. However, Felix’s version will only need to complete two passes.

Explain how Felix may have made his version more efficient than Darcie’s version.

A second type of sorting algorithm is an insertion sort.

Describe how an insertion sort can be used to put the following data into ascending order.

A third type of sorting algorithm is a quick sort.

The following quick sort algorithm is made up of two functions called partition() and quickSort(). The algorithm will sort an integer array into ascending numerical order.

Identify which of the two functions is recursive and give all of the line numbers where recursive calls are made.

Recursive function name........

Recursive call line numbers........

Identify the type of iteration used in the function partition().

Describe the role of the function partition() in the quick sort algorithm.

The algorithm needs to be changed to sort the integer array into descending numerical order.

Identify the line number that needs to be changed and write the amended line of code.

Amended line of code........

The quick sort is an example of a divide-and-conquer algorithm.

Describe what divide-and-conquer means.

A recursive pseudocode function, recursiveAlgorithm(), is shown.

Describe the key features of a recursive algorithm.

You may refer to the function, recursiveAlgorithm() in your answer.

Trace the recursive function, recursiveAlgorithm(), and give the final return value when called with recursiveAlgorithm(10). You may choose to use the table below to give your answer.

Final return value........

A program uses the recursive function calculate(). The function is written in pseudocode.

Give the line number in the algorithm calculate() where a recursive call is made.

State two features of any recursive algorithm.

Trace the recursive function calculate() and give the final return value, when the following function call is run:

calculate(5)

You may choose to use the table below to give your answer.

Give the pseudocode function call that would return 55 from the recursive function calculate().

Hugh has written a recursive function called thisFunction() using pseudocode.

The function DIV calculates integer division, e.g. 5 DIV 3 = 1

State the name of the standard algorithm thisFunction() performs.

Hugh could have written thisFunction() using iteration instead of recursion.

Compare two differences between recursion and iteration.

The recursive function thisFunction() is printed again here for your reference.

Rewrite the function thisFunction() so that it uses iteration instead of recursion.

You should write your answer using pseudocode or program code.

A recursive function, GCD, is given in pseudocode.

The function uses branching.

Identify the type of branching statement used in the function.

Explain the difference between branching and iteration.

Identify the two parameters in the function.

1

2.

State whether the parameters should be passed by value, or by reference. Justify your answer.

Describe the arithmetic operation of MOD. Use an example in your answer.

Trace the recursive function when it is called by the statement GCD(250, 20). Give the final value returned.

Final return value:.

The function has been rewritten using iteration instead of recursion.

State one benefit and one drawback of using iteration instead of recursion.

Benefit.

Drawback.

Complete the missing statements in this iterative version of the function.

A recursive function, generate, is shown.

Trace the algorithm to show the value returned when generate(7) is called. Show each step of your working.

The parameter, num1, is passed by value.

Explain why the parameter was passed by value instead of by reference.

* Parameters can be used to reduce the use of global variables.

Compare the use of parameters to global variables in recursive functions.

A student called Jason writes a recursive algorithm. The recursive algorithm uses more memory than if Jason had written it as an iterative algorithm.

Explain why the recursive algorithm uses more memory than the iterative algorithm.

A recursive function, calculate, is shown below:

Identify the lines where recursion is used.

Trace the algorithm, showing the steps and result when the following line is run:

print(calculate(4,10))

Re-write the function so it uses iteration instead of recursion.