How to stop bash from creating subshells when recu

Question

This is a simple shell function to calculate factorial.

#!/bin/bash

function factorial()
{
   if (( $1 < 2 ))
   then
     echo 1
   else
     echo $(( $1 * $(factorial $(( $1 - 1 ))) ))
   fi
}

factorial $1

But I find that this script will create many sub-shells when given a very big input. It is not necessary and not efficient. Is there any way to call recursive functions without creating new sub-shells?

My goal is not how to write a factorial function in shell, but how to avoid creating sub-shells when call recursively defined functions.

In fact, even a simple function call will cause creation of sub-shells:

#!/bin/bash

function fac0() {
  ps >> log
  echo $1
}

function fac1() {
  ps >> log
  echo $(( $1 * $(fac0 $(( $1 - 1 ))) ))
}

touch log
fac1 $1

After run the script, the log file's content is: (It still creates sub-shells)

  PID TTY          TIME CMD
 9205 pts/8    00:00:00 bash
 9245 pts/8    00:00:00 call_subshell.s
 9247 pts/8    00:00:00 ps
  PID TTY          TIME CMD
 9205 pts/8    00:00:00 bash
 9245 pts/8    00:00:00 call_subshell.s
 9248 pts/8    00:00:00 call_subshell.s
 9249 pts/8    00:00:00 ps

Because of sub-shell creation, other unwanted aspects exist.

#!/bin/bash

declare -i i
i=0

function factorial() {
   i=$(($i + 1))
   if (( $1 < 2 ))
   then
     echo 1
   else
     local c=$(( $1 - 1 ))
     echo $(( $1 * $(factorial $c) ))
   fi
}

factorial $1
echo $i

This script will print $i=1 no matter what number the argument is!

Answer 1

Avoid the recursion:

#!/bin/bash
factorial() {
    local f=1
    for ((i=2; i<=$1; i++)) ; do
        (( f *= i ))
    done
    echo $f
}

factorial $1

The subshell is spawned because of command substitution. Use a "argument as a result" way to avoid it:

#!/bin/bash

# set -xv

factorial() {
    # echo $BASH_SUBSHELL
    if [[ $2 ]] ; then
        if (( $2 == 1 )) ; then
            echo $1
        else
            factorial $(( $1 * $2 )) $(( $2 - 1 ))
        fi
    else
        factorial $1 $(( $1 - 1 ))
    fi
}

factorial $1

Answer 2

One need only separate the calculation from the function call and use the 'let' builtin. If there were commands in the parameters, use the 'eval' builtin rather than $(). Not as elegant, perhaps, but avoids subshells.

if [[ $2 ]] ; then
    if (( $2 == 1 )) ; then
        echo $1
    else
        let "p1=$1*$2"
        let "p2 = $2-1"
        factorial $p1 $p2
    fi
else
    let "p2 = $1-1"
    factorial $1 $p2
fi