Recursion

Review : Abstraction

Describing Functions

: A function's domain is the set of all inputs it might possibly take as arguments

: A function's range is the set of output values it might possibly return

: A pure function's behavior is the relationship it creates between input and output

Functional Abstraction

Mechanics

: How does python execute this program line-by-line

: What happens when you evaluate a call expression, what goes on its body

Use (functional abstraction)

-   square(2) always return 4

-   square(3) always return 9

without worrying about how python evaluates the function

 

Recursion

( iterative algorithm / recursive algorithm )

: useful for solving problems with a naturally repeating structure _ they are defined in terms of themselves

It requires you to find patterns of smaller problems, and to define the smallest problem possible

Recursion in Evaluation

f ( g ( h (2), True ), h(x) )

: A call expression is composed of smaller ( call ) expressions !

: Stop once you reach a number, boolean, name, etc

Recursive Functions

-   A function is called recursive if the body of that function calls itself, either directly or indirectly

-   This implies that executing the body of a recursive function may require applying that function multiple times

-   Recursion is inherently tied to functional abstraction

Structure of a Recursive Function

1. One or more base cases, usually the smallest input

 : If you're at the front, you know you're first

2. One or more ways of reducing the problem, and then solving the smaller problem using recursion

 : Ask the person in front, 'What number in line are you ?'

3. One or more ways of using the solutionto each smaller problem to solve our larger problem

 : When the person in front of you figures it out and tells you, add one to that answer

Functional Abstraction & Recursion

Expression    Value

fact(1)            1

fact(3)           6 ( 3*2*1)

fact(n)           n * n-1 * ... * 1 = n * fact(n-1)

Verifying factorial

Q Is factorial correct ?

1. Verify the base cases

   Q Are they correct ?

   Q Are they exhaustive ?

 : Now harness the power of functional abstraction

2. Assume that factorial(n-1) is correct

3. Verify that factorial(n) is correct

Functional abstraction : don't worry that factorial is recursive and just assume that factorial gets the right answer

Visualizing Recursion

Recursion in Environment Diagrams

-   The same function fact is called multiple times, each time solving a simpler problem

-   All the frames share the same parent-only difference is the argument

-   What n evaluates to depends upon the current environment

Recursive tree _ another way to visualize recursion

How to Trust functional abstraction

Look at how we computed fact(3)

Which  required computing fact(2)

Which  required computing fact(1)

Which  required computing fact(0)

Which we know is 1, thanks to the base case !

Verifying the correctness of recursive functions

1. Verify that the base cases work as expected

2. For each larger case, verify that it works by assuming the smaller recursive calls are correct

Identifying patterns

Is factorial correct ?

1. List out all the cases

2. Identify patterns between each cases

3. Simplify repeated codes with recursive calls

Count Up

1. One or more base cases

_ What is the smallest number where we don't have to do any work ?

2. One or more recursive calls with simpler arguments

_ Have access to the largest number, so try printing smaller numbers

3. Using the recursive call to solve our larger problem

_ Once we've printed up to n-1, what value is left ?

Iteration vs Recursion

-   Iteration and recursion are somewhat related

-   Converting iternationto recursion is formulaic, but converting recursion to iteration can be more tricky

 

Summary

-   Recursive functions are functions that call themselves in their body one or more times

: This allows us to break the problem down into smaller pieces

: Using functional abstraction, we do not have to worry about how those smaller problems are solved

-   A recursive function has a base cases to define its smallest problem, and one or more recursive calls

: If we know the base case is correct, and that we get the correct solution assuming the recursive calls work, then we know the function is correct

-   Evaluating recursive calls follow the same rules we've talked about so far