Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Recursion:See Recursion

Slides from the Leeds Code Dojo session
by

Grant Crofton

on 3 March 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Recursion:See Recursion

Recursion:
What?
Why?!
How?!
Dictionary
"The repeated application of a recursive procedure or definition"
Programming
"A function which calls itself"
How to think of it
Iteration Requires State
Suits some problems better
e.g.

Fibonacci
Factorial
Word Wrap
Quicksort
File System search
Drawing Trees...
Iterative vs Recursive: Factorial
It's Fun!
Structure of a recursive function
Always remember the base case!
Factorial - Trace
See Recursion
Leeds Code Dojo
"Solving a problem using solutions to smaller instances of the same problem"
"Factorial: The product of an integer and all positive integers below it"
Base Case (AKA Terminating Case)
Recursive case (must move towards base case)
Tail Call Optimisation
The Problem: Stack Overflow
State stored on the stack

Stack is a limited size

sum_recursive [1..60000] -> 1800030000

sum_recursive [1..65000] -> StackOverflowException
The Solution:
Tail Calls
Passing accumulator means not necessary to maintain stack

Usually done with second function so accumulator hidden from caller

Only if your compiler supports TCO
Continuations
Continuations:
What?
Collect results in a (series of) function(s)
Continuations:
Why
Functions with multiple recursion can't use tail calls, e.g. with a tree data structure.

Passing the state in functions makes this possible
Continuations:
How
http://lmgtfy.com/?q=continuations
Returns a function, which when called gets answer
sum_continuations [1..5] (fun sum ->
printfn "Answer: %i" sum)
Good luck!
Full transcript