### Present Remotely

Send the link below via email or IM

• 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

Do you really want to delete this prezi?

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

# Recursion:See Recursion

Slides from the Leeds Code Dojo session
by

## Grant Crofton

on 3 March 2015

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 ->