Recursive Functions in Fortran

Recursion is a programming technique where a function calls itself to solve a problem. Recursive functions are particularly useful for problems that can be divided into smaller, similar subproblems. In Fortran, recursion can simplify tasks such as calculating factorials, Fibonacci sequences, and other mathematical or algorithmic operations. This post provides a detailed explanation of recursive functions in Fortran, including syntax, examples, and practical applications.

1. Introduction to Recursion

A recursive function is a function that calls itself within its definition.

• The function must have a base case to terminate the recursion.
• Each recursive call should move the problem closer to the base case.
• Recursive functions can replace iterative loops in some scenarios.

Advantages of Recursion

1. Simplifies code for problems naturally defined in terms of themselves (factorials, Fibonacci numbers).
2. Reduces the need for explicit loops in some algorithms.
3. Can improve readability for divide-and-conquer algorithms.

Disadvantages of Recursion

1. May consume more memory due to call stack overhead.
2. Can be slower than iterative solutions for large inputs.
3. Requires careful handling to avoid infinite recursion.

---

2. Syntax of Recursive Functions in Fortran

In Fortran, recursive functions require the recursive keyword:

recursive function function_name(arguments) result(result_variable)
! declarations
type_of_result :: result_variable
type_of_arguments :: arguments
! function body
end function function_name

• recursive tells the compiler that the function may call itself.
• result(result_variable) names the function’s return value explicitly.

---

3. Example: Factorial Using Recursion

The factorial of a number n is defined as:

• factorial(n) = n * factorial(n-1) for n > 1
• factorial(1) = 1 (base case)

Code Example

program main
print *, "Factorial of 5:", factorial(5)
end program main

recursive function factorial(n) result(fact)
integer :: fact
integer, intent(in) :: n
if (n <= 1) then
    fact = 1
else
    fact = n * factorial(n-1)
end if
end function factorial

Explanation:

• factorial(5) calls factorial(4), which calls factorial(3), and so on.
• Base case n <= 1 stops recursion.
• The function multiplies values back up the call stack.

Output:

Factorial of 5: 120

---

4. Step-by-Step Execution of Factorial

1. factorial(5) → 5 * factorial(4)
2. factorial(4) → 4 * factorial(3)
3. factorial(3) → 3 * factorial(2)
4. factorial(2) → 2 * factorial(1)
5. factorial(1) → 1 (base case)
6. Multiply back up: 2 * 1 = 2 → 3 * 2 = 6 → 4 * 6 = 24 → 5 * 24 = 120

This demonstrates how recursion unwinds after reaching the base case.

---

5. Fibonacci Sequence Using Recursion

The Fibonacci sequence is defined as:

• fib(0) = 0
• fib(1) = 1
• fib(n) = fib(n-1) + fib(n-2) for n > 1

Code Example

program main
integer :: i
do i = 0, 10
    print *, "Fib(", i, ") =", fibonacci(i)
end do
end program main

recursive function fibonacci(n) result(fib)
integer :: fib
integer, intent(in) :: n
if (n == 0) then
    fib = 0
else if (n == 1) then
    fib = 1
else
    fib = fibonacci(n-1) + fibonacci(n-2)
end if
end function fibonacci

Explanation:

• Base cases: n = 0 or n = 1.
• Recursive calls reduce the problem size until reaching base cases.
• Output:

Fib(0) = 0
Fib(1) = 1
Fib(2) = 1
Fib(3) = 2
Fib(4) = 3
Fib(5) = 5
Fib(6) = 8
Fib(7) = 13
Fib(8) = 21
Fib(9) = 34
Fib(10) = 55

---

6. Tail Recursion vs Non-Tail Recursion

• Tail recursion: The recursive call is the last operation in the function. Optimizers can sometimes convert tail recursion into iteration for efficiency.
• Non-tail recursion: The function performs additional calculations after the recursive call.

Factorial Example (Tail Recursive Version)

recursive function factorial_tail(n, acc) result(fact)
integer :: fact
integer, intent(in) :: n, acc
if (n <= 1) then
    fact = acc
else
    fact = factorial_tail(n-1, n*acc)
end if
end function factorial_tail

program test
print *, "Factorial of 5 (tail recursion):", factorial_tail(5, 1)
end program test

• Uses an accumulator acc to store intermediate results.
• Can be more memory-efficient than standard recursion.

---

7. Recursive Sum of an Array

Recursion can process arrays element by element.

Code Example

program main
integer, dimension(5) :: arr = (/1, 2, 3, 4, 5/)
print *, "Sum of array:", sum_array(arr, 5)
end program main

recursive function sum_array(arr, n) result(sum)
integer :: sum
integer, intent(in) :: arr(:)
integer, intent(in) :: n
if (n == 0) then
    sum = 0
else
    sum = arr(n) + sum_array(arr, n-1)
end if
end function sum_array

Explanation:

• Base case: n = 0 → sum = 0
• Recursive case: add arr(n) to sum of remaining elements
• Output:

Sum of array: 15

---

8. Recursive Binary Search

Recursion is useful for divide-and-conquer algorithms like binary search.

program main
integer, dimension(5) :: arr = (/1, 3, 5, 7, 9/)
integer :: target
target = 5
print *, "Index of", target, ":", binary_search(arr, target, 1, 5)
end program main

recursive function binary_search(arr, key, low, high) result(idx)
integer :: idx
integer, intent(in) :: arr(:)
integer, intent(in) :: key, low, high
integer :: mid
if (low > high) then
    idx = -1
else
    mid = (low + high) / 2
    if (arr(mid) == key) then
        idx = mid
    else if (arr(mid) > key) then
        idx = binary_search(arr, key, low, mid-1)
    else
        idx = binary_search(arr, key, mid+1, high)
    end if
end if
end function binary_search

• Searches for key recursively by halving the array each time.
• Output:

Index of 5 : 3

---

9. Practical Applications of Recursive Functions

1. Mathematical computations: factorial, Fibonacci, power, combinatorial calculations.
2. Data structures: recursion is used to traverse trees or graphs (if implemented in Fortran).
3. Algorithms: divide-and-conquer, binary search, mergesort.
4. Dynamic programming: recursive formulations for optimization problems.
5. Simulations: recursive modeling of processes like branching or fractals.

---

10. Best Practices for Recursive Functions

1. Always define a base case to avoid infinite recursion.
2. Keep recursion depth reasonable to prevent stack overflow.
3. Use tail recursion when possible to improve efficiency.
4. Document the function clearly, specifying arguments and return value.
5. Avoid unnecessary recursion for problems that are easily solved iteratively.

---

11. Common Pitfalls

1. Infinite recursion: Missing or incorrect base case.
2. Stack overflow: Too many recursive calls for large inputs.
3. Redundant computation: E.g., naive Fibonacci recursion recalculates values repeatedly.
4. Incorrect argument passing: Ensure all recursive calls move toward the base case.