Week 5 - Inducing, reducing and recursing.

Question 1

What is induction?

Answer 1

induction, or proof by induction, is generally used to prove propositions that are statements about natural number (N).

Question 2

What is recursion?

Answer 2

Recursion is a computational technique that involves a function calling itself. It can be used in the algorithmic quest to break down a problem into smaller and smaller sub-problems.

Question 3

What are the authors’ three laws of recursion?

Answer 3

A recursive algorithm must:

a) have a base case - usually a simple version of the problem that can be solved directly.
b) involve a state-change that moves the problem stepwise towards the base case.
c) calls itself.

Question 4

What do the authors mean by the term stack frame?

Answer 4

A stack frame is a record of the local variables, along with their values, that a recursive function is using each time it calls itself.