# 24.3. Recursion Without Local Variables

A function may recursively call itself even without use of local variables.

Example 24-16. The Fibonacci Sequence

 #!/bin/bash # fibo.sh : Fibonacci sequence (recursive) # Author: M. Cooper # License: GPL3 # ----------algorithm-------------- # Fibo(0) = 0 # Fibo(1) = 1 # else # Fibo(j) = Fibo(j-1) + Fibo(j-2) # --------------------------------- MAXTERM=15 # Number of terms (+1) to generate. MINIDX=2 # If idx is less than 2, then Fibo(idx) = idx. Fibonacci () { idx=\$1 # Doesn't need to be local. Why not? if [ "\$idx" -lt "\$MINIDX" ] then echo "\$idx" # First two terms are 0 1 ... see above. else (( --idx )) # j-1 term1=\$( Fibonacci \$idx ) # Fibo(j-1) (( --idx )) # j-2 term2=\$( Fibonacci \$idx ) # Fibo(j-2) echo \$(( term1 + term2 )) fi # An ugly, ugly kludge. # The more elegant implementation of recursive fibo in C #+ is a straightforward translation of the algorithm in lines 7 - 10. } for i in \$(seq 0 \$MAXTERM) do # Calculate \$MAXTERM+1 terms. FIBO=\$(Fibonacci \$i) echo -n "\$FIBO " done # 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 # Takes a while, doesn't it? Recursion in a script is slow. echo exit 0

Example 24-17. The Towers of Hanoi