Understanding Recursion in Computer Science

Recursion is a powerful concept in computer science that involves breaking down a problem into smaller, more manageable parts until a base case is reached and solved directly. By utilizing functions that call themselves, recursion offers an elegant way to solve complex problems. This post delves into the essence of recursion, providing examples, comparisons with iteration, and illustrations to enhance your understanding of this fundamental concept.

• Recursion
• Divide and Conquer
• Computer Science
• Algorithms

jaan752 Follow

Uploaded on Sep 20, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Recursion In essence, divide and conquer, where you reduce a problem to a simpler version of the problem until you arrive at something that you can solve directly! Uses functions The function calls itself It stops until a base case is met. A base case is something you can solve directly More intuitive and simpler to use (once you are used to recursion) 4! = 4 * 3* 2* 1 n! = n * (n-1) * (n-2) * (n-3) * * 1 def factorial_recu (n): if n == 1: return 1 else: return n * factorial_recu(n-1) def factorial_iter(n): prod = 1 for i in range(1, n+1): prod = prod*i return prod

2. Iteration def factorial_iter(n): prod = 1 for i in range(1, n+1): prod = prod*i return prod Round i Prod Comments 1 1 1 1! 2 2 1 * 2 2! 3 3 1 * 2 * 3 3! 4 4 1 * 2 * 3*4 4! n n 1 * 2 * 3 *n n!

3. Recursion def f_r (n): if n == 1: return 1 else: return n * f_r(n-1) Now we can solve backwards Round n n * factorial_recu(n- 1) factorial_recu(n- 1) Return value Effective outcome 1 n n * f_r(n-1) f_r(n-1) ? 1 * 2 * 3 * 4..*n n! 2 n-1 (n-1) * f_r(n-2) f_r(n-2) ? 1 * 2 * 3 * 4 *n-1! (n-1)! 3 n-2 (n-2) * f_r(n-3) f_r(n-3) ? 1 * 2 * 3 * 4 (n-2)! 4 n-3 (n-3) * f_r(n-4) f_r(n-4) ? 1 * 2 * 3 * 4 (n-3)! n 1 (n-(n-1))*f_r(n-n) f_r(n-n) 1 1 1!

4. Recursion def fact_recu (n): if n == 1: return 1 else: return n * factorial_recu(n-1) factorial_recu (4) def fact_recu (4): if n == 1: # nope return 1 else: return n * fact_recu(4-1) return 4 * fact_recu(3)

5. Recursion def fact_recu (n): if n == 1: return 1 else: return n * factorial_recu(n-1) factorial_recu (4) def fact_recu (4): if n == 1: # nope return 1 else: return n * fact_recu(4-1) def fact_recu (3): if n == 1: # nope return 1 else: return n * fact_recu(3-1) return 4 * fact_recu(3) return 3 * fact_recu(2)

6. Recursion def fact_recu (n): if n == 1: return 1 else: return n * factorial_recu(n-1) factorial_recu (4) def fact_recu (2): if n == 1: # nope return 1 else: return n * fact_recu(2-1) def fact_recu (4): if n == 1: # nope return 1 else: return n * fact_recu(4-1) def fact_recu (3): if n == 1: # nope return 1 else: return n * fact_recu(3-1) return 2 * fact_recu(1) return 4 * fact_recu(3) return 3 * fact_recu(2)

7. Recursion def fact_recu (n): if n == 1: return 1 else: return n * factorial_recu(n-1) factorial_recu (4) def fact_recu (1): if n == 1: # Yes! return 1 def fact_recu (2): if n == 1: # nope return 1 else: return n * fact_recu(2-1) def fact_recu (4): if n == 1: # nope return 1 else: return n * fact_recu(4-1) def fact_recu (3): if n == 1: # nope return 1 else: return n * fact_recu(3-1) return 2 * fact_recu(1) return 4 * fact_recu(3) return 3 * fact_recu(2) return 1 #base case!

8. Recursion def fact_recu (n): if n == 1: return 1 else: return n * factorial_recu(n-1) factorial_recu (4) def fact_recu (1): if n == 1: # Yes! return 1 def fact_recu (2): if n == 1: # nope return 1 else: return n * fact_recu(2-1) def fact_recu (4): if n == 1: # nope return 1 else: return n * fact_recu(4-1) def fact_recu (3): if n == 1: # nope return 1 else: return n * fact_recu(3-1) return 2 * fact_recu(1) return 4 * fact_recu(3) return 3 * fact_recu(2) return 1 #base case! 1

9. Recursion def fact_recu (n): if n == 1: return 1 else: return n * factorial_recu(n-1) factorial_recu (4) def fact_recu (1): if n == 1: # Yes! return 1 def fact_recu (2): if n == 1: # nope return 1 else: return n * fact_recu(2-1) def fact_recu (4): if n == 1: # nope return 1 else: return n * fact_recu(4-1) def fact_recu (3): if n == 1: # nope return 1 else: return n * fact_recu(3-1) return 2 * fact_recu(1) return 4 * fact_recu(3) return 3 * fact_recu(2) return 1 #base case! 2 * 1

10. Recursion def fact_recu (n): if n == 1: return 1 else: return n * factorial_recu(n-1) factorial_recu (4) def fact_recu (1): if n == 1: # Yes! return 1 def fact_recu (2): if n == 1: # nope return 1 else: return n * fact_recu(2-1) def fact_recu (4): if n == 1: # nope return 1 else: return n * fact_recu(4-1) def fact_recu (3): if n == 1: # nope return 1 else: return n * fact_recu(3-1) return 2 * fact_recu(1) return 4 * fact_recu(3) return 3 * fact_recu(2) return 1 #base case! 3 * 2 * 1

11. Recursion def fact_recu (n): if n == 1: return 1 else: return n * factorial_recu(n-1) factorial_recu (4) def fact_recu (1): if n == 1: # Yes! return 1 def fact_recu (2): if n == 1: # nope return 1 else: return n * fact_recu(2-1) def fact_recu (4): if n == 1: # nope return 1 else: return n * fact_recu(4-1) def fact_recu (3): if n == 1: # nope return 1 else: return n * fact_recu(3-1) return 2 * fact_recu(1) return 4 * fact_recu(3) return 3 * fact_recu(2) return 1 #base case! 3 * 2 * 1 4 *

12. 1. The sum f(n) = 1 + 2 + 3 + 4 + 5 + + n can be defined as a recursive function: f(0) = 0 if n == 0 f(n) = n + f(f-1) if n > 0 Write a recursion function my_add to calculate the sum of a number sequence.

13. 1. The sum f(n) = 1 + 2 + 3 + 4 + 5 + + n can be defined as a recursive function: f(0) = 0 if n == 0 f(n) = n + f(n-1) if n > 0 Write a recursion function my_add to calculate the sum of a number sequence. Solution: def my_add(n): # use recursive function to calculate the sum of a number # the base case if n == 0: return 0 # otherwise, we apply the recursive formula else: return n + my_add(n - 1) sequence print(my_add(100)) # the result is 5050 = 1 + 2 + 3 + + 100