wk3&&4(recursion)

Define recursion?

Recursion is a technique whereby a problem is expressed in a similar form to the original problem but smaller in scope.

What are the two requirements of a recursive algorithm?

Solution is easy to specify for certain conditions – stopping case. Rules for proceeding to a new state which is either a stopping case or eventually leads to a stopping case – recursive steps

Explain Stopping case/base case

The known answer the smallest value that one that can be fed back in to the function

Explain the recursive step

All other cases that are not the base case that will cal back the function/method

When should you not use recursion?

if no to any of the following: the algorithm/data structure naturally suited to recursion? Is the recursive solution shorter and more understandable? Does the recursive solution run in acceptable time limits and/or space limits?

What is tail end recursion?

there is one recursive call in an algorithm and this call is the very last thing the done.

What is back tracking?

Backtracking is a systematic trial and error approach to finding the solution to a problem.