Iterative and Recursive Functions in Python

Iterative Functions

• Definition: An iterative function is a function that uses loops (such as while or for) to execute a repeated block of code.
• Implementation Example (PROG 5.35-FactorialIterative.py):
  • Calculates the factorial of a non-negative number iteratively using a for loop.

# Python program to find the factorial of a number iteratively
def fact_iter (num):
    factorial=1
    for i in range(1, num+1):
        factorial *= i
    return(factorial)

n = int(input("Enter number whose factorial you want to calculate = "))
fact = fact_iter(n)
print("Factorial of ",n," = ", fact)

• Program Execution Output:

==== RESTART: D:\PYTHON\CHAP PROGRAMS\Chap Function\FactorialIterative.py
Enter number whose factorial you want to calculate = 3
Factorial of  3  =  6

Recursive Functions

• Definition: A function is called a recursive function if it calls itself repeatedly within its body until a specified stopping condition is satisfied.

• Application: Recursion is well-suited for repetitive problems where each action can be expressed in terms of a previous result.

• Core Requirements of Recursion:

  1. The function must call itself repeatedly.
  2. The function must have a clear stopping condition (base case).

• Mathematical Formulation of Factorial:

  • $0! = 1$
  • $1! = 1$
  • $n! = n \times (n - 1)!, \text{ where } n > 0$

• Implementation Example (PROG 5.36-FactorialRecursion.py):

  • Calculates the factorial of a user-provided positive integer recursively.

# Python program to find the factorial of a number using recursion
def fact_rec(n):
    if n == 0:
        return 1
    else:
        return n * fact_rec(n-1)

n = int(input("Enter number whose factorial you want to calculate = "))
fact = fact_rec(n)
print("Factorial of ",n," = ", fact)

• Program Execution Output:

==== RESTART: D:\PYTHON\CHAP PROGRAMS\Chap Function\FactorialRecursion.py
Enter number whose factorial you want to calculate = 3
Factorial of  3  =  6

• Execution Trace for Recursive Call (fact_rec(3) - Fig. 5.9):
  • Upon executing fact = fact_rec(n) with $n = 3$, control shifts to fact_rec.
  • It checks if parameter $n == 0$. If true, it returns $1$.
  • If $n \neq 0$ (here $n = 3$), it returns $n$ multiplied by fact_rec(n - 1) (which is fact_rec(2)).
  • The function recursively invokes itself with decreasing values of $n$ until $n = 0$ is reached.
  • Recursive Step Decomposition:
  • $\text{fact\_rec}(3) = 3 \times \text{fact\_rec}(2)$
  • $\text{fact\_rec}(2) = 2 \times \text{fact\_rec}(1)$
  • $\text{fact\_rec}(1) = 1 \times \text{fact\_rec}(0)$
  • Base Case: $\text{fact\_rec}(0) = 1$
  • Unwinding / Return Value Calculations:
  • $\text{fact\_rec}(1) = 1 \times 1 = 1$
  • $\text{fact\_rec}(2) = 2 \times 1 = 2$
  • $\text{fact\_rec}(3) = 3 \times 2 = 6$

Detailed Comparison: Iteration vs Recursion

Both recursion and iteration accomplish similar tasks, but differ in execution mechanism, control structures, performance, and implementation constraints:

• 1. Basic Definition & Execution:

  • Iteration: Uses a loop structure to repeatedly execute a set of statements until a controlling condition becomes false.
  • Recursion: A technique where a function calls itself repeatedly until a defined base condition is met.

• 2. Control Structure:

  • Iteration: Uses a repetition structure.
  • Recursion: Uses a selection structure (if-else branching logic).

• 3. Termination Condition:

  • Iteration: Terminates when the loop continuation condition fails (evaluates to false).
  • Recursion: Terminates when the base case is met or recognized.

• 4. Problem-Solving Methodology:

  • Iteration: Repeatedly executes statements until a loop counter reaches a defined limit.
  • Recursion: Solves a complex problem by breaking it down into progressively smaller sub-problems until a solvable base case is reached, subsequently combining results during stack unwinding.

• 5. Required Steps:

  • Iteration: Involves 4 distinct steps: initialization, condition checking, execution of internal loop statements, and updating (increment/decrement).
  • Recursion: Requires only the base condition to be explicitly specified.

• 6. Failure Modes (Infinite Execution):

  • Iteration: An infinite loop occurs if the loop continuation condition never fails.
  • Recursion: Infinite recursion occurs if the recursion step fails to reduce the problem size in a manner that converges upon the base case (leading to stack overflow).

• 7. Code Size and Simplicity:

  • Iteration: Iterative implementations tend to make program code longer.
  • Recursion: Recursive implementations make program code shorter and simpler.

• 8. Speed and Memory Overhead:

  • Iteration: Faster than recursion because it simply iterates without storing intermediate execution frames on the stack.
  • Recursion: Slower due to the memory overhead of maintaining function call stack frames for each call.

• 9. Scope of Application:

  • Iteration: Can be applied directly to any block or set of statements that require repeated execution.
  • Recursion: Always applied specifically to functions.