Recursion

What Is Recursion?

  • Recursion is a technique where a function calls itself. It allows for solutions to problems that can be broken down into smaller, repetitive tasks.

Recursive Function in Python:

  • Here's a basic structure of a recursive function:

    python
    def myFunc():
    ...
    myFunc()
    ...

Examples:

  1. Factorial:

    • A function to calculate the factorial of a number using recursion.

      python
      def factorial(x):
    if x < 1:
        return 1
    else:
        return x * factorial(x - 1)

print(factorial(0))  # Output: 1
print(factorial(1))  # Output: 1
print(factorial(2))  # Output: 2
print(factorial(3))  # Output: 6
print(factorial(4))  # Output: 24
  2. Fibonacci Series:

    • A function to calculate the nth element of the Fibonacci series using recursion.

      python
      def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

n = 10
fibo_series = [fibonacci(i) for i in range(n)]
print(fibo_series)  # Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Exercises:

  1. Sum of Natural Numbers:

    • Write a recursive function to calculate the sum of the first n natural numbers.

      python
      def sum_natural_numbers(n):
    if n <= 1:
        return n
    else:
        return n + sum_natural_numbers(n - 1)

print(sum_natural_numbers(10))  # Output: 55
  2. Power Function:

    • Write a recursive function to calculate the power of a number.

      python
      def power(base, exp):
    if exp == 0:
        return 1
    else:
        return base * power(base, exp - 1)

print(power(2, 3))  # Output: 8

Summary:

  • Recursion is a powerful technique in Python that involves functions calling themselves. It’s used to solve problems that can be divided into smaller, similar problems. Practice writing recursive functions to get comfortable with this concept!