Documentation
¶
Overview ¶
Package tailrec provides a trampoline implementation for tail-call optimization in Go.
Overview ¶
Go does not support tail-call optimization (TCO) at the language level, which means deeply recursive functions can cause stack overflow errors. The trampoline pattern provides a way to convert recursive algorithms into iterative ones, avoiding stack overflow while maintaining the clarity of recursive code.
A trampoline works by returning instructions about what to do next instead of directly making recursive calls. The trampoline executor then interprets these instructions in a loop, effectively converting recursion into iteration.
Core Concepts ¶
The package provides three main operations:
**Bounce**: Indicates that the computation should continue with a new value. This represents a recursive call in the original algorithm.
**Land**: Indicates that the computation is complete and returns a final result. This represents the base case in the original algorithm.
**Unwrap**: Extracts the state from a Trampoline, allowing the executor to determine whether to continue (Bounce) or terminate (Land).
Type Parameters ¶
The Trampoline type has two type parameters:
- B: The "bounce" type - the intermediate state passed between recursive steps
- L: The "land" type - the final result type when computation completes
Basic Usage ¶
Converting a recursive factorial function to use trampolines:
// Traditional recursive factorial (can overflow stack)
func factorial(n int) int {
if n <= 1 {
return 1
}
return n * factorial(n-1)
}
// Trampoline-based factorial (stack-safe)
type State struct {
n int
acc int
}
func factorialStep(state State) tailrec.Trampoline[State, int] {
if state.n <= 1 {
return tailrec.Land[State](state.acc)
}
return tailrec.Bounce[int](State{state.n - 1, state.acc * state.n})
}
// Execute the trampoline
func factorial(n int) int {
current := tailrec.Bounce[int](State{n, 1})
for {
bounce, land, isLand := tailrec.Unwrap(current)
if isLand {
return land
}
current = factorialStep(bounce)
}
}
Fibonacci Example ¶
Computing Fibonacci numbers with tail recursion:
type FibState struct {
n int
curr int
prev int
}
func fibStep(state FibState) tailrec.Trampoline[FibState, int] {
if state.n <= 0 {
return tailrec.Land[FibState](state.curr)
}
return tailrec.Bounce[int](FibState{
n: state.n - 1,
curr: state.prev + state.curr,
prev: state.curr,
})
}
func fibonacci(n int) int {
current := tailrec.Bounce[int](FibState{n, 1, 0})
for {
bounce, land, isLand := tailrec.Unwrap(current)
if isLand {
return land
}
current = fibStep(bounce)
}
}
List Processing Example ¶
Summing a list with tail recursion:
type SumState struct {
list []int
sum int
}
func sumStep(state SumState) tailrec.Trampoline[SumState, int] {
if len(state.list) == 0 {
return tailrec.Land[SumState](state.sum)
}
return tailrec.Bounce[int](SumState{
list: state.list[1:],
sum: state.sum + state.list[0],
})
}
func sumList(list []int) int {
current := tailrec.Bounce[int](SumState{list, 0})
for {
bounce, land, isLand := tailrec.Unwrap(current)
if isLand {
return land
}
current = sumStep(bounce)
}
}
Integration with Reader Monads ¶
The tailrec package is commonly used with Reader monads (readerio, context/readerio) to implement stack-safe recursive computations that also depend on an environment:
import (
"github.com/IBM/fp-go/v2/readerio"
"github.com/IBM/fp-go/v2/tailrec"
)
type Env struct {
Multiplier int
}
func compute(n int) readerio.ReaderIO[Env, int] {
return readerio.TailRec(
n,
func(n int) readerio.ReaderIO[Env, tailrec.Trampoline[int, int]] {
return func(env Env) func() tailrec.Trampoline[int, int] {
return func() tailrec.Trampoline[int, int] {
if n <= 0 {
return tailrec.Land[int](n * env.Multiplier)
}
return tailrec.Bounce[int](n - 1)
}
}
},
)
}
Benefits ¶
- **Stack Safety**: Prevents stack overflow for deep recursion
- **Clarity**: Maintains the structure of recursive algorithms
- **Performance**: Converts recursion to iteration without manual rewriting
- **Composability**: Works well with functional programming patterns
When to Use ¶
Use trampolines when:
- You have a naturally recursive algorithm
- The recursion depth could be large (thousands of calls)
- You want to maintain the clarity of recursive code
- You're working with functional programming patterns
Performance Considerations ¶
While trampolines prevent stack overflow, they do have some overhead:
- Each step allocates a Trampoline struct
- The executor loop adds some indirection
For shallow recursion (< 1000 calls), direct recursion may be faster. For deep recursion, trampolines are essential to avoid stack overflow.
Key Functions ¶
**Bounce**: Create a trampoline that continues computation with a new state
**Land**: Create a trampoline that terminates with a final result
**Unwrap**: Extract the state and determine if computation should continue
See Also ¶
- readerio.TailRec: Tail-recursive Reader IO computations
- context/readerio.TailRec: Tail-recursive Reader IO with context
Example (Collatz) ¶
Example_collatz demonstrates the Collatz conjecture using trampolines.
package main
import (
"fmt"
"github.com/IBM/fp-go/v2/tailrec"
)
func main() {
// Define the step function
collatzStep := func(n int) tailrec.Trampoline[int, int] {
if n <= 1 {
return tailrec.Land[int](n)
}
if n%2 == 0 {
return tailrec.Bounce[int](n / 2)
}
return tailrec.Bounce[int](3*n + 1)
}
// Execute the trampoline and count steps
collatzSteps := func(n int) int {
current := tailrec.Bounce[int](n)
steps := 0
for {
if current.Landed {
return steps
}
current = collatzStep(current.Bounce)
steps++
}
}
// Count steps for Collatz sequence starting at 27
result := collatzSteps(27)
fmt.Printf("Collatz(27) takes %d steps to reach 1\n", result)
}
Output: Collatz(27) takes 112 steps to reach 1
Example (Countdown) ¶
Example_countdown demonstrates a simple countdown using trampolines.
package main
import (
"fmt"
"github.com/IBM/fp-go/v2/tailrec"
)
func main() {
// Define the step function
countdownStep := func(n int) tailrec.Trampoline[int, int] {
if n <= 0 {
return tailrec.Land[int](0)
}
return tailrec.Bounce[int](n - 1)
}
// Execute the trampoline
countdown := func(n int) int {
current := tailrec.Bounce[int](n)
for {
if current.Landed {
return current.Land
}
current = countdownStep(current.Bounce)
}
}
// Countdown from 5
result := countdown(5)
fmt.Printf("countdown(5) = %d\n", result)
}
Output: countdown(5) = 0
Example (DeepRecursion) ¶
Example_deepRecursion demonstrates handling deep recursion without stack overflow.
package main
import (
"fmt"
"github.com/IBM/fp-go/v2/tailrec"
)
func main() {
// Define the step function
countdownStep := func(n int) tailrec.Trampoline[int, int] {
if n <= 0 {
return tailrec.Land[int](0)
}
return tailrec.Bounce[int](n - 1)
}
// Execute the trampoline
countdown := func(n int) int {
current := tailrec.Bounce[int](n)
for {
if current.Landed {
return current.Land
}
current = countdownStep(current.Bounce)
}
}
// This would cause stack overflow with regular recursion
// but works fine with trampolines
result := countdown(100000)
fmt.Printf("countdown(100000) = %d (no stack overflow!)\n", result)
}
Output: countdown(100000) = 0 (no stack overflow!)
Example (Factorial) ¶
Example_factorial demonstrates implementing factorial using trampolines.
package main
import (
"fmt"
"github.com/IBM/fp-go/v2/tailrec"
)
func main() {
type State struct {
n int
acc int
}
// Define the step function
factorialStep := func(state State) tailrec.Trampoline[State, int] {
if state.n <= 1 {
return tailrec.Land[State](state.acc)
}
return tailrec.Bounce[int](State{state.n - 1, state.acc * state.n})
}
// Execute the trampoline
factorial := func(n int) int {
current := tailrec.Bounce[int](State{n, 1})
for {
if current.Landed {
return current.Land
}
current = factorialStep(current.Bounce)
}
}
// Calculate factorial of 5
result := factorial(5)
fmt.Printf("5! = %d\n", result)
}
Output: 5! = 120
Example (Fibonacci) ¶
Example_fibonacci demonstrates computing Fibonacci numbers using trampolines.
package main
import (
"fmt"
"github.com/IBM/fp-go/v2/tailrec"
)
func main() {
type State struct {
n int
curr int
prev int
}
// Define the step function
fibStep := func(state State) tailrec.Trampoline[State, int] {
if state.n <= 0 {
return tailrec.Land[State](state.curr)
}
return tailrec.Bounce[int](State{
n: state.n - 1,
curr: state.prev + state.curr,
prev: state.curr,
})
}
// Execute the trampoline
fibonacci := func(n int) int {
current := tailrec.Bounce[int](State{n, 1, 0})
for {
if current.Landed {
return current.Land
}
current = fibStep(current.Bounce)
}
}
// Calculate 10th Fibonacci number
result := fibonacci(10)
fmt.Printf("fib(10) = %d\n", result)
}
Output: fib(10) = 89
Example (FieldAccess) ¶
Example_fieldAccess demonstrates accessing trampoline fields directly.
package main
import (
"fmt"
"github.com/IBM/fp-go/v2/tailrec"
)
func main() {
// Create a bounce trampoline
bounceTramp := tailrec.Bounce[string](42)
fmt.Printf("Bounce: value=%d, landed=%v\n", bounceTramp.Bounce, bounceTramp.Landed)
// Create a land trampoline
landTramp := tailrec.Land[int]("result")
fmt.Printf("Land: value=%s, landed=%v\n", landTramp.Land, landTramp.Landed)
}
Output: Bounce: value=42, landed=false Land: value=result, landed=true
Example (Gcd) ¶
Example_gcd demonstrates computing greatest common divisor using trampolines.
package main
import (
"fmt"
"github.com/IBM/fp-go/v2/tailrec"
)
func main() {
type State struct {
a int
b int
}
// Define the step function (Euclidean algorithm)
gcdStep := func(state State) tailrec.Trampoline[State, int] {
if state.b == 0 {
return tailrec.Land[State](state.a)
}
return tailrec.Bounce[int](State{state.b, state.a % state.b})
}
// Execute the trampoline
gcd := func(a, b int) int {
current := tailrec.Bounce[int](State{a, b})
for {
if current.Landed {
return current.Land
}
current = gcdStep(current.Bounce)
}
}
// Calculate GCD of 48 and 18
result := gcd(48, 18)
fmt.Printf("gcd(48, 18) = %d\n", result)
}
Output: gcd(48, 18) = 6
Example (SumList) ¶
Example_sumList demonstrates processing a list using trampolines.
package main
import (
"fmt"
"github.com/IBM/fp-go/v2/tailrec"
)
func main() {
type State struct {
list []int
sum int
}
// Define the step function
sumStep := func(state State) tailrec.Trampoline[State, int] {
if len(state.list) == 0 {
return tailrec.Land[State](state.sum)
}
return tailrec.Bounce[int](State{
list: state.list[1:],
sum: state.sum + state.list[0],
})
}
// Execute the trampoline
sumList := func(list []int) int {
current := tailrec.Bounce[int](State{list, 0})
for {
if current.Landed {
return current.Land
}
current = sumStep(current.Bounce)
}
}
// Sum a list of numbers
numbers := []int{1, 2, 3, 4, 5}
result := sumList(numbers)
fmt.Printf("sum([1,2,3,4,5]) = %d\n", result)
}
Output: sum([1,2,3,4,5]) = 15
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Trampoline ¶
type Trampoline[B, L any] struct { // Land holds the final result value when the computation has completed. // This field is only meaningful when Landed is true. Land L // Bounce holds the intermediate state for the next recursive step. // This field is only meaningful when Landed is false. Bounce B // Landed indicates whether the computation has completed. // When true, the Land field contains the final result. // When false, the Bounce field contains the state for the next iteration. Landed bool }
Trampoline represents a step in a tail-recursive computation.
A Trampoline can be in one of two states:
- Bounce: The computation should continue with a new intermediate state (type B)
- Land: The computation is complete with a final result (type L)
Type Parameters ¶
- B: The "bounce" type - intermediate state passed between recursive steps
- L: The "land" type - the final result type when computation completes
The trampoline pattern allows converting recursive algorithms into iterative ones, preventing stack overflow for deep recursion while maintaining code clarity.
Design Note ¶
This type uses a struct with a boolean flag rather than the Either type to avoid a cyclic dependency. The either package depends on tailrec for its own tail-recursive operations, so using Either here would create a circular import.
Example ¶
// Factorial using trampolines
type State struct { n, acc int }
func factorialStep(state State) Trampoline[State, int] {
if state.n <= 1 {
return Land[State](state.acc) // Base case
}
return Bounce[int](State{state.n - 1, state.acc * state.n}) // Recursive case
}
See package documentation for more examples and usage patterns.
func Bounce ¶
func Bounce[L, B any](b B) Trampoline[B, L]
Bounce creates a Trampoline that indicates the computation should continue with a new intermediate state.
This represents a recursive call in the original algorithm. The computation will continue by processing the provided state value in the next iteration.
Type Parameters ¶
- B: The intermediate state type (bounce type)
- L: The final result type (land type)
Parameters ¶
- b: The new intermediate state to process in the next step
Returns ¶
- Trampoline[B, L]: A Trampoline in the "bounce" state containing the intermediate value
Example ¶
// Countdown that bounces until reaching zero
func countdownStep(n int) Trampoline[int, int] {
if n <= 0 {
return Land[int](0)
}
return Bounce[int](n - 1) // Continue with n-1
}
Example ¶
ExampleBounce demonstrates creating a trampoline that continues computation.
package main
import (
"fmt"
"github.com/IBM/fp-go/v2/tailrec"
)
func main() {
// Create a bounce trampoline with value 42
tramp := tailrec.Bounce[string](42)
// Access fields directly to inspect the state
fmt.Printf("Is computation complete? %v\n", tramp.Landed)
fmt.Printf("Next value to process: %d\n", tramp.Bounce)
}
Output: Is computation complete? false Next value to process: 42
func Land ¶
func Land[B, L any](l L) Trampoline[B, L]
Land creates a Trampoline that indicates the computation is complete with a final result.
This represents the base case in the original recursive algorithm. When a Land trampoline is encountered, the executor should stop iterating and return the final result.
Type Parameters ¶
- B: The intermediate state type (bounce type)
- L: The final result type (land type)
Parameters ¶
- l: The final result value
Returns ¶
- Trampoline[B, L]: A Trampoline in the "land" state containing the final result
Example ¶
// Factorial base case
func factorialStep(state State) Trampoline[State, int] {
if state.n <= 1 {
return Land[State](state.acc) // Computation complete
}
return Bounce[int](State{state.n - 1, state.acc * state.n})
}
Example ¶
ExampleLand demonstrates creating a trampoline that completes computation.
package main
import (
"fmt"
"github.com/IBM/fp-go/v2/tailrec"
)
func main() {
// Create a land trampoline with final result
tramp := tailrec.Land[int]("done")
// Access fields directly to inspect the state
fmt.Printf("Is computation complete? %v\n", tramp.Landed)
fmt.Printf("Final result: %s\n", tramp.Land)
}
Output: Is computation complete? true Final result: done
func (Trampoline[B, L]) Format ¶
func (t Trampoline[B, L]) Format(f fmt.State, verb rune)
Format implements fmt.Formatter for Trampoline.
Supports various formatting verbs for detailed output:
- %v: Default format (delegates to String)
- %+v: Detailed format with type information
- %#v: Go-syntax representation (delegates to GoString)
- %s: String format
- %q: Quoted string format
Parameters ¶
- f: The format state
- verb: The formatting verb
func (Trampoline[B, L]) GoString ¶
func (t Trampoline[B, L]) GoString() string
GoString implements fmt.GoStringer for Trampoline.
Returns a Go-syntax representation that could be used to recreate the value. The output includes the package name, function name, type parameters, and value.
Returns ¶
- string: A Go-syntax representation of the trampoline
func (Trampoline[B, L]) LogValue ¶
func (t Trampoline[B, L]) LogValue() slog.Value
LogValue implements the slog.LogValuer interface for Trampoline.
This method allows Trampoline values to be logged using Go's structured logging with proper representation of their state:
- When Landed is true: returns a group with a single "landed" attribute containing the Land value
- When Landed is false: returns a group with a single "bouncing" attribute containing the Bounce value
The implementation ensures that Trampoline values are logged in a structured, readable format that clearly shows the current state of the tail-recursive computation.
Returns ¶
- slog.Value: A structured log value representing the trampoline state
Example ¶
trampoline := tailrec.Bounce[int](42)
slog.Info("Processing", "state", trampoline)
// Logs: {"level":"info","msg":"Processing","state":{"bouncing":42}}
result := tailrec.Land[int](100)
slog.Info("Complete", "result", result)
// Logs: {"level":"info","msg":"Complete","result":{"landed":100}}
This is particularly useful for debugging tail-recursive computations and understanding the flow of recursive algorithms at runtime.
func (Trampoline[B, L]) String ¶
func (t Trampoline[B, L]) String() string
String implements fmt.Stringer for Trampoline.
Returns a human-readable string representation of the trampoline state. For bounce states, returns "Bounce(value)". For land states, returns "Land(value)".
Returns ¶
- string: A formatted string representation of the trampoline state
Source Files