Understanding Recursion in Python: A Beginner-Friendly Guide Part 2
Today, we'll walk through some fun and practical examples of more recursion in Python, all without using any built-in shortcuts or helper functions. Problem 1: Reverse a String Using Recursion Problem: Write a function reverse_string(s) that returns the reversed version of string s. Breakdown: If the string is empty or has one character, return it. Otherwise, take the last character and append it to the reversed substring. Solution: def reverse_string(s): if len(s) int: memo = {} def fib_helper(n: int) -> int: if n in memo: return memo[n] if n == 0: return 0 elif n == 1: return 1 memo[n] = fib_helper(n - 1) + fib_helper(n - 2) return memo[n] return fib_helper(n) Example: fibonacci(7) # Output: 13 Final Thoughts Recursion teaches us to think differently, breaking down problems into smaller chunks until we reach a base case. While it's tempting to lean on built-in functions, solving problems recursively helps build a deeper understanding of logic and control flow. Try these problems out yourself, tweak them, and challenge yourself to come up with variations. Recursion might just become your favorite problem-solving tool!
Today, we'll walk through some fun and practical examples of more recursion in Python, all without using any built-in shortcuts or helper functions.
Problem 1: Reverse a String Using Recursion
Problem:
Write a function reverse_string(s) that returns the reversed version of string s.
Breakdown:
- If the string is empty or has one character, return it.
- Otherwise, take the last character and append it to the reversed substring.
Solution:
def reverse_string(s):
if len(s) <= 1:
return s
else:
return s[-1] + reverse_string(s[:-1])
Example:
reverse_string("hello") # Output: "olleh"
Problem 2: Fibonacci with Memoization (O(n) Time)
Problem:
Return the nth Fibonacci number using recursion with memoization to improve performance.
Breakdown:
- Use a helper function with a memo dictionary.
- Cache results to avoid redundant calculations.
Solution:
def fibonacci(n: int) -> int:
memo = {}
def fib_helper(n: int) -> int:
if n in memo:
return memo[n]
if n == 0:
return 0
elif n == 1:
return 1
memo[n] = fib_helper(n - 1) + fib_helper(n - 2)
return memo[n]
return fib_helper(n)
Example:
fibonacci(7) # Output: 13
Final Thoughts
Recursion teaches us to think differently, breaking down problems into smaller chunks until we reach a base case. While it's tempting to lean on built-in functions, solving problems recursively helps build a deeper understanding of logic and control flow.
Try these problems out yourself, tweak them, and challenge yourself to come up with variations. Recursion might just become your favorite problem-solving tool!
