Skip to content

Instantly share code, notes, and snippets.

@logosity logosity/
Created May 9, 2012

What would you like to do?
Tail Recursion in 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
# or (assuming nothing else is running sleep):
# kill $(ps -f | grep sleep | grep -v grep | awk '{print $3}')

This comment has been minimized.

Copy link

commented Aug 6, 2016

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:


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


This comment has been minimized.

Copy link

commented Aug 7, 2016

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
You can’t perform that action at this time.