Recursion repeats a computation by having a function call itself. Each call needs to move toward a base case: a condition that returns a result without making another recursive call. It offers an alternative to repeating work with a `while` or `for` loop. section 3.10.1 section 3.10.2
When the stopping condition is missing
The Julia definition `fac(n) = n*fac(n-1)` looks like a way to calculate factorial. But decreasing `n` is not enough: `fac` keeps calling itself even after `n` falls below 1, eventually producing a `StackOverflowError`. An `if` statement can provide the missing exit. section 3.6
Fibonacci numbers give recursion a natural shape. To calculate a number beyond the first two, add the two preceding numbers: `fib(n-1) + fib(n-2)`. For `n` equal to 0 or 1, return `n` instead. Those first two results are the base cases that stop the calls. section 3.10 section 3.10.1
Listing 3.17 Calculating a Fibonacci number
function fib(n)
if n == 0 #1
0
elseif n == 1 #1
1
else
fib(n-1) + fib(n-2) #2
end
end
The Julia `fib` listing puts its stopping cases before the calls that calculate smaller Fibonacci numbers. section 3.10
The same calculation can use a loop. An iterative Fibonacci function tracks earlier values and updates them on each pass, requiring more bookkeeping than the recursive version. Recursion can be simpler to write, but is often slower; if performance becomes a problem, iteration is an option. section 3.10.2
Listing 3.19 Calculating a Fibonacci number using iteration
function fibi(n)
if 0 <= n <= 1
return n #1
end
prev = 0 #2
x = 1 #3
for i in 2:n
tmp = x
x += prev #4
prev = tmp
end
x
end
Compare the iterative Fibonacci listing with the recursive one: the loop replaces self-calls with variables that track previous results. section 3.10.2
