Recursive functions in Bash Scripting - Time & Space Complexity

Time Complexity: Recursive functions

O(n)

Understanding Time Complexity

When we use recursive functions in bash scripting, it is important to understand how the time needed grows as the input gets bigger.

We want to know how many times the function calls itself and how that affects the total work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

factorial() {
  local n=$1
  if (( n <= 1 )); then
    echo 1
  else
    local prev=$(factorial $((n - 1)))
    echo $((n * prev))
  fi
}

factorial 5

This code calculates the factorial of a number using recursion, calling itself with smaller numbers until it reaches 1.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The function calls itself once per number from n down to 1.
• How many times: Exactly n times, where n is the input number.

How Execution Grows With Input

Each time we increase n by 1, the function makes one more recursive call, so the total work grows steadily.

Input Size (n)	Approx. Operations
10	10 calls
100	100 calls
1000	1000 calls

Pattern observation: The number of calls grows directly with n, so doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the size of the input number.

Common Mistake

[X] Wrong: "Recursive functions always take much longer than loops because they call themselves many times."

[OK] Correct: In this case, the recursive function calls itself once per step, just like a loop would. So the time grows the same way as a simple loop.

Interview Connect

Understanding how recursion grows helps you explain your code clearly and shows you can think about efficiency, which is a great skill in scripting and automation.

Self-Check

"What if the recursive function called itself twice each time? How would the time complexity change?"