Recursion in Python

Our example demonstrates recursive functions in Python. Here’s a classic example:

import sys

# This `fact` function calls itself until it reaches the
# base case of `fact(0)`.
def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

def main():
    print(fact(7))

    # In Python, we don't need to explicitly declare the type of a function
    # before defining it. We can define a recursive lambda function directly.
    fib = lambda n: n if n < 2 else fib(n-1) + fib(n-2)

    print(fib(7))

if __name__ == "__main__":
    main()

This code defines two recursive functions:

1. fact(n): A classic factorial function that recursively calculates the factorial of a given number.
2. fib(n): A Fibonacci sequence generator implemented as a lambda function.

In the main() function, we call both of these recursive functions with an argument of 7 and print the results.

To run the program, save it as recursion.py and use the Python interpreter:

$ python recursion.py
5040
13

The output shows:

• 5040, which is 7! (7 factorial)
• 13, which is the 7th number in the Fibonacci sequence (counting from 0)

Note that in Python, we don’t need to explicitly declare function types before defining them, as we would in some statically typed languages. This allows us to define the recursive lambda function for Fibonacci directly.

Also, be cautious with recursive functions in Python, as they can lead to stack overflow for large inputs due to Python’s recursion limit. For production use, especially with large inputs, consider using iterative solutions or techniques like memoization to optimize recursive functions.