Skip to content

Instantly share code, notes, and snippets.

@logosity
Created May 9, 2012 20:33
Show Gist options
  • Save logosity/2648596 to your computer and use it in GitHub Desktop.
Save logosity/2648596 to your computer and use it in GitHub Desktop.
Tail Recursion in bash
#!/bin/bash
# warning you need to build in something to stop the loop
# in practice, I used a kill file check before invoking the script again
echo 'tail recursive bash ftw'
sleep 10
$0 &
# if you didn't listen and ran this as-is, try:
# killall tail.sh
# or (assuming nothing else is running sleep):
# kill $(ps -f | grep sleep | grep -v grep | awk '{print $3}')
@chuckhoupt
Copy link

Amusing, and hard to kill! This isn't so much "tail recursion" as "tail spawning", because the last line spawns a new process.

I think the correct way to tail recurse in Bash is to use exec. For example, to print even integers:

#!/bin/bash

N=${1:-0}
echo "Proc $$: ${N}-th Even Integer: " $(( $N * 2 ))
sleep 1

exec "$0" $(( $N + 1 ))

The advantage of exec is that it implements a form of tail call elimination, since the exec-ed command replaces the current process, avoiding stacked processes. The recursion can continue forever while using a constant amount of memory/processes. It also makes it easy to kill!

Cheers - Chuck

@chuckhoupt
Copy link

Follow-up: The Racket developer Jay McCarthy has a good explanation of how exec works in "exec and Tail-call Optimization".

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment