Introduction to Python Recursion

Introduction to Programming in Python: Recursion

• Recursion is a function calling itself to solve smaller problem instances.
• It's a technique of divide and conquer, breaking problems into simpler, manageable parts.
• Recursion mimics Russian nesting dolls, with a set of problem instances nested within another.
• Recursion has a finite depth; it must have a base case to stop the chain of calls.
• Main components of recursion:
  • Base case: A condition that terminates the recursion.
  • Recursive case: The function call itself on a smaller problem.

Factorial

• Factorial, denoted as n!, is the product of all positive integers less than or equal to n.
• Examples:
  • 0! = 1 (no positive integers less than 1)
  • 1! = 1
  • 2! = 2 * 1 = 2
  • 3! = 3 * 2 * 1 = 6
  • 4! = 4 * 3 * 2 * 1 = 24

Example Recursive Factorial

• Implement a recursive function to compute the factorial of a number.

Programming is a Process (Revisited)

• Analysis: Problem analysis and specification.
• Design: Breaking down problems into smaller sub-problems and formulating algorithms.
• Coding: Implementing the solutions in code.
• Testing: Testing code functionality.
• Debugging: Identifying and fixing bugs.

Example Recursive Factorial: Analysis

• Ensure understanding of the mathematical definition of factorial (only for non-negative integers).
• Determine the requirements:
  • Input data is a positive integer.
  • Output is an integer (the factorial).

Example Recursive Factorial: Design

• Determine a suitable function name (e.g., factorial).
• Define the parameters (e.g., n, for the number).
• Identify the base case (e.g., 0! or 1! equal 1).
• Determine the recursive case (e.g., n! = n * (n-1)!).

Example Recursive Factorial: Coding (Incorrect Approach)

• A wrong approach is to manually enumerate the products for each case, an impractical method on large numbers.
• This is a less elegant method of computing factorials recursively.

Example Recursive Factorial: Coding (Correct Approach)

• The recursive case includes:
  • elif n == 2: return 2 * factorial(2 - 1);
  • elif n == 3: return 3 * factorial(3 - 1);

Example Recursive Factorial: Coding (Polishing Code)

• Base case: if n == 0 or n == 1: return 1
• Recursive case: else: return n * factorial(n-1)

Example Recursive Factorial: Testing (by using doctest)

• Include a docstring to clearly explain the function's purpose, input parameters, and return type.
• Use doctests for testing different input values.

Exercise 14.1: Python Tutor

• Use Python Tutor to visualize the execution of the factorial function.

Exercise 14.1: Python Tutor (Observer)

• Observe how Python keeps track of recursive function calls.

Fibonacci

• A sequence where each number is the sum of the two preceding ones (e.g., 0, 1, 1, 2, 3...).

Exercise 14.2: Recursive Fibonacci

• Implement the Fibonacci sequence recursively.

Exercise 14.3: Counting Hashtags

• Recursively count hashtags (strings starting with '#').

Exercise 14.3: Counting Hashtags (Polished)

• A polished and efficient recursive method for computing hashtags, with optimal considerations for base cases.

Exercise 14.3: Counting Hashtags (Hack)

• A concise recursive method for computing hashtags.

Exercise 14.4: Extracting Hashtags

• Recursively extract hashtags from a list of strings.

Exercise 14.5: Fibonacci Spiral

• Create a spiral visual representation of the Fibonacci sequence using tiles.

Tile Orientation

• Tiles rotate as they are added to the spiral (0°, 90°, 180°, 270°, then back to 0°, etc.)
• The orient function handles these rotations.

Best Practices about Recursion

• Infinite Loops: Ensure a proper base case for recursion to terminate.
• Deep Recursion: Be aware that Python has a limit on recursion depth.
• Inefficient Fibonacci Computation: Recursively computing Fibonacci numbers can become very slow for large numbers; use memoization or iterative solutions.
• Inefficient List Operations: Recursive operations on large lists can be much slower than using other Python techniques.