Recursion(not finished) & Recursive Data Structures(deffo not finished) & Recurrence Relation (finished)

What is recursion?

defining a function (or problem) in terms of itself

(solving a problem by solving a smaller version of the same problem)

What 2 things does every recursive definition need?

• Base case

  • simplest input, answered directly, so the recursion stops

• Recursive case

  • reduces the problem to a smaller version of itself

What is “divide and conquer”?

• divide problem into smaller problems that are easier to solve

• combine solutions of small problems = solution to big problem

Towers of Hanoi

3 stages

1. move top n-1 disks from start peg to spare peg

2. move largest disk froms start peg to destination peg

3. move n-1 disks from spare peg to destination peg

Recurrence relation:

• two recursive calls: T(n-1)

• one disk movement O(1)

• therefore reccurrence relation: T(n) = 2T(n-1) + O(1)

• recurrence produces exponential growth therefore time complexity is O(2^n)

What is the general structure of a recursive function

How would a binary tree search be written as a recursive function?

What is recurrence relation?

• mathemetical equation

• describes running time of a recursive algorithm in terms of the running time of its smaller recursive calls

  • tells us how much time an algorithm takes by looking at:

    • time taken by recursive calls

    • additional work performed outside those calls

In recurrence relation what is the additional work represented as in big O notation?

O(1) - constant time

How would you calculate the recurrence relation for working out a factorial?

• factorial algorithm performs:

  1. one recursive call : factorial(n-1)

     • takes T(n-1)

  2. one multiplication

     • takes O(1)

  3. contstant amount of additional work

     1. takes O(1)

• therefore the running time is T(n) = O(n)

When looking at normal and efficicent exponentiation why is the efficient version better?

dividing the input by 2 reduces number of recursive calls mcuh faster than subtracting one each time

How do you derive the recurrence relation in an exam?

1. Count the recursive calls

   • how many times does the function call itself?

2. Identify size of each recursive input

   • look at how the input changes

   • does it decrease by 1 (n-1)? decrease by half (n/2)?

3. Calculate additional work

   • what happens outside recursive calls

   • e.g. O(1) when multiplication/comparison/loop through all n elements

4. Write recurrence

   • put recursive calls & additional work together