12.2 Simple math recursion

Recursive algorithms in mathematics break problems into smaller subproblems, solving them recursively until reaching a base case. This approach is key to mathematical induction and efficient problem-solving in computer science.

From factorials to Fibonacci sequences, recursion offers elegant solutions to complex mathematical problems. Understanding recursive case vs. base case, and considering efficiency, are crucial for implementing effective recursive algorithms in programming.

Recursive Algorithms in Mathematics

Recursive case vs base case

Top images from around the web for Recursive case vs base case

• 

  Calculando factoriales de números grandes – KS7000+WP View original

  Is this image relevant?

• 

  Factorial | AlgoRitmia View original

  Is this image relevant?

• 

  Reading 10: Recursion View original

  Is this image relevant?

• 

  Calculando factoriales de números grandes – KS7000+WP View original

  Is this image relevant?

• 

  Factorial | AlgoRitmia View original

  Is this image relevant?

1 of 3

Top images from around the web for Recursive case vs base case

• 

  Calculando factoriales de números grandes – KS7000+WP View original

  Is this image relevant?

• 

  Factorial | AlgoRitmia View original

  Is this image relevant?

• 

  Reading 10: Recursion View original

  Is this image relevant?

• 

  Calculando factoriales de números grandes – KS7000+WP View original

  Is this image relevant?

• 

  Factorial | AlgoRitmia View original

  Is this image relevant?

1 of 3

• Recursive algorithms break down problems into smaller subproblems solved recursively until reaching a base case
• Base case is the condition where recursion stops, typically the smallest possible input or a case with a known solution (0! = 1)
• Prevents infinite recursion by providing a termination condition
• Recursive case is the condition where the function calls itself with a modified input
• Breaks down the problem into smaller subproblems progressing towards the base case (n! = n × (n-1)! for n > 0)
• This approach is fundamental to mathematical induction, where a property is proven for a base case and then shown to hold for all cases

Factorial calculation with recursion

• Factorial of a non-negative integer $n$ is the product of all positive integers less than or equal to $n$ ($5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$)
• Denoted as $n!$
• Recursive definition of factorial:
  1. Base case: $0! = 1$
  2. Recursive case: $n! = n \times (n-1)!$ for $n > 0$
• Recursive function to calculate factorial:

  [def](https://www.fiveableKeyTerm:def) factorial(n):
      if n == 0:
          [return](https://www.fiveableKeyTerm:Return) 1
      else:
          return n * factorial(n - 1)
  

Recursive functions for math problems

• Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones (0, 1, 1, 2, 3, 5, 8, 13, ...)
• Recursive definition:
  1. Base cases: $F(0) = 0$ and $F(1) = 1$
  2. Recursive case: $F(n) = F(n-1) + F(n-2)$ for $n > 1$
• Recursive function to calculate the nth Fibonacci number:

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

• Greatest common divisor (GCD) is the largest positive integer that divides each of the integers (gcd(48, 18) = 6)
• Euclidean algorithm:
  1. Base case: $gcd(a, 0) = a$
  2. Recursive case: $gcd(a, b) = gcd(b, a \mod b)$ for $b \neq 0$
• Recursive function to calculate GCD:

  def gcd(a, b):
      if b == 0:
          return a
      else:
          return gcd(b, a % b)
  

Efficiency considerations in recursive algorithms

• Time complexity: Measure of how the execution time of an algorithm increases with input size
• Space complexity: Measure of the memory usage of an algorithm as input size grows
• Divide-and-conquer: A strategy where a problem is broken down into smaller subproblems, solved recursively, and then combined to solve the original problem