Send the link below via email or IMCopy
Present to your audienceStart 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
Transcript of Recursion:See Recursion
"The repeated application of a recursive procedure or definition"
"A function which calls itself"
How to think of it
Iteration Requires State
Suits some problems better
File System search
Iterative vs Recursive: Factorial
Structure of a recursive function
Always remember the base case!
Factorial - Trace
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
Passing accumulator means not necessary to maintain stack
Usually done with second function so accumulator hidden from caller
Only if your compiler supports TCO
Collect results in a (series of) function(s)
Functions with multiple recursion can't use tail calls, e.g. with a tree data structure.
Passing the state in functions makes this possible
Returns a function, which when called gets answer
sum_continuations [1..5] (fun sum ->
printfn "Answer: %i" sum)