Lesson 18 of 55
10 mins readRecursion Patterns & Tail Recursion
In Plain English
Because Haskell has no while or for loops, recursion is the fundamental mechanism for repetition. Learn standard recursion and tail-call optimized accumulator patterns.
Deep Dive: How It Works
Structure of Recursion: Base case (returns non-recursive value) + Recursive step (calls itself on a smaller subproblem).
Tail Recursion: The recursive call is the final expression executed, allowing compiler stack frame reuse.
Accumulator Pattern: Pass intermediate state down as an argument to make functions tail-recursive.
Core Rules to Remember
Recursion as Loop Primitive: Iterate over data structures declaratively through base and recursive equations.
Accumulators for Tail Recursion: Ensure O(1) constant stack space usage for deep iterative calculations.
Live Interactive Example
Hit Run Code to see it liveStandard vs Tail Recursive Factorial
Python 3.12
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Output Console
Click "Run Code" to view the rendered output.
How it works: go uses tail recursion to accumulate the product without growing the call stack.
Your Turn: Micro Challenge
No pressure! Edit the starter code below and test your solution with instant feedback.
Micro Exercise
Write Recursive Fibonacci
- Define `fib 0 = 0`, `fib 1 = 1`, and `fib n = fib (n - 1) + fib (n - 2)`.
- Print `"Fib(7): "` followed by `show (fib 7)`.
1
2
3
4
5
6
7
8
9
Sandbox Output
Click "Run & Check" to test your solution.
Finished reading and practicing?
Mark this lesson as completed to update your course progress.