0
# Trampolines
1

2
Tail-call optimization utilities that convert recursive functions into iterative ones to avoid stack overflow errors. This enables safe recursion in Python for functional programming patterns.
3

4
## Capabilities
5

6
### Trampoline Container
7

8
A container that represents a computation step in a recursive algorithm, enabling tail-call optimization.
9

10
```python { .api }
11
class Trampoline[T]:
12
    """Container for tail-call optimized recursion"""
13
    def __init__(self, computation: Callable[[], Trampoline[T] | T]): ...
14
    
15
    def run(self) -> T:
16
        """Execute the trampoline until completion"""
17
        
18
    def bind(self, func: Callable[[T], Trampoline[U]]) -> Trampoline[U]:
19
        """Bind a function returning Trampoline"""
20
        
21
    def map(self, func: Callable[[T], U]) -> Trampoline[U]:
22
        """Transform the final result"""
23

24
    @classmethod
25
    def done(cls, value: T) -> Trampoline[T]:
26
        """Create a completed trampoline"""
27
        
28
    @classmethod  
29
    def call(cls, func: Callable[[], Trampoline[T] | T]) -> Trampoline[T]:
30
        """Create a trampoline from a thunk"""
31
```
32

33
### Trampoline Decorator
34

35
Convert recursive functions to use trampolines automatically.
36

37
```python { .api }
38
def trampoline(func: Callable[..., Trampoline[T]]) -> Callable[..., T]:
39
    """Convert trampoline-returning function to regular function"""
40
```
41

42
## Usage Examples
43

44
### Basic Tail Recursion
45

46
```python
47
from returns.trampolines import Trampoline, trampoline
48

49
# Traditional recursive factorial (stack overflow risk)
50
def factorial_recursive(n: int, acc: int = 1) -> int:
51
    if n <= 1:
52
        return acc
53
    return factorial_recursive(n - 1, acc * n)
54

55
# Trampoline version (stack safe)
56
def factorial_trampoline(n: int, acc: int = 1) -> Trampoline[int]:
57
    if n <= 1:
58
        return Trampoline.done(acc)
59
    return Trampoline.call(lambda: factorial_trampoline(n - 1, acc * n))
60

61
@trampoline  
62
def factorial(n: int) -> Trampoline[int]:
63
    return factorial_trampoline(n)
64

65
# Safe for large numbers
66
result = factorial(10000)  # No stack overflow
67
```
68

69
### Mutual Recursion
70

71
```python
72
from returns.trampolines import Trampoline, trampoline
73

74
def is_even_trampoline(n: int) -> Trampoline[bool]:
75
    if n == 0:
76
        return Trampoline.done(True)
77
    return Trampoline.call(lambda: is_odd_trampoline(n - 1))
78

79
def is_odd_trampoline(n: int) -> Trampoline[bool]:
80
    if n == 0:
81
        return Trampoline.done(False)
82
    return Trampoline.call(lambda: is_even_trampoline(n - 1))
83

84
@trampoline
85
def is_even(n: int) -> Trampoline[bool]:
86
    return is_even_trampoline(n)
87

88
@trampoline    
89
def is_odd(n: int) -> Trampoline[bool]:
90
    return is_odd_trampoline(n)
91

92
# Safe for large numbers
93
result = is_even(100000)  # True, no stack overflow
94
```
95

96
### List Processing
97

98
```python
99
from returns.trampolines import Trampoline, trampoline
100
from typing import List
101

102
def sum_list_trampoline(items: List[int], acc: int = 0) -> Trampoline[int]:
103
    if not items:
104
        return Trampoline.done(acc)
105
    return Trampoline.call(
106
        lambda: sum_list_trampoline(items[1:], acc + items[0])
107
    )
108

109
@trampoline
110
def sum_list(items: List[int]) -> Trampoline[int]:
111
    return sum_list_trampoline(items)
112

113
# Process large lists safely  
114
large_list = list(range(50000))
115
total = sum_list(large_list)  # No stack overflow
116
```
117

118
### Trampoline with Container Integration
119

120
```python
121
from returns.trampolines import Trampoline, trampoline
122
from returns.result import Result, Success, Failure
123
from returns.maybe import Maybe, Some, Nothing
124

125
def safe_divide_recursive(
126
    dividend: float, 
127
    divisor: float, 
128
    depth: int = 0
129
) -> Trampoline[Result[float, str]]:
130
    if depth > 100:
131
        return Trampoline.done(Failure("Maximum recursion depth reached"))
132
    
133
    if divisor == 0:
134
        return Trampoline.done(Failure("Division by zero"))
135
        
136
    if dividend < 1:
137
        return Trampoline.done(Success(dividend))
138
        
139
    # Continue dividing
140
    return Trampoline.call(
141
        lambda: safe_divide_recursive(dividend / divisor, divisor, depth + 1)
142
    )
143

144
@trampoline
145
def safe_divide_until_small(dividend: float, divisor: float) -> Trampoline[Result[float, str]]:
146
    return safe_divide_recursive(dividend, divisor)
147

148
# Safe recursive division
149
result = safe_divide_until_small(1000000.0, 2.0)  # Success(small_number)
150
```
151

152
## Performance Benefits
153

154
Trampolines provide several advantages for recursive algorithms:
155

156
1. **Stack Safety**: Eliminates stack overflow errors for deep recursion
157
2. **Memory Efficiency**: Uses constant stack space regardless of recursion depth  
158
3. **Composability**: Works with other functional programming constructs
159
4. **Debugging**: Easier to debug than traditional recursion
160

161
## When to Use Trampolines
162

163
Use trampolines when:
164

165
- Implementing naturally recursive algorithms (factorial, fibonacci, tree traversal)
166
- Processing large data structures recursively
167
- Converting imperative loops to functional style
168
- Implementing recursive descent parsers
169
- Working with recursive data structures (linked lists, trees)
170

171
Trampolines enable safe functional programming patterns that would otherwise be limited by Python's recursion depth limit.