Recursion in Python is a technique where a function calls itself directly or indirectly to solve a problem. It’s a powerful concept often used in algorithms that break down a problem into smaller, more manageable parts. Here’s an in-depth look at recursion in Python with various examples to illustrate how it can be applied.

### Basic Recursion Example: Factorial

The factorial of a number is the product of all positive integers less than or equal to that number. For example, the factorial of 5 (denoted as 5!) is 5 x 4 x 3 x 2 x 1 = 120.

**Example**:

1 2 3 4 5 6 7 |
def factorial(n): if n == 1: return 1 else: return n * factorial(n-1) print(factorial(5)) # Output: 120 |

### Indirect Recursion

Indirect recursion occurs when a function is called not by itself but by another function that it, in turn, calls.

**Example**:

1 2 3 4 5 6 7 8 9 10 11 12 13 |
def functionA(n): if n == 0: return print('A:', n) functionB(n-1) def functionB(n): if n == 0: return print('B:', n) functionA(n-1) functionA(5) |

### Fibonacci Sequence

The Fibonacci sequence is a series where each number is the sum of the two preceding ones, usually starting with 0 and 1. It’s a classic example of a problem that can be solved using recursion.

**Example**:

1 2 3 4 5 6 7 |
def fibonacci(n): if n <= 1: return n else: return fibonacci(n-1) + fibonacci(n-2) print(fibonacci(10)) # Output: 55 |

### Handling Base Cases in Recursion

It’s crucial to define a base case in recursive functions to prevent infinite recursion. The base case returns a value without making further recursive calls.

**Example**:

1 2 3 4 5 6 7 8 |
def count_down(n): if n <= 0: print("Liftoff!") else: print(n) count_down(n-1) count_down(5) |

### Tower of Hanoi

The Tower of Hanoi is a classic problem that involves moving a stack of disks from one rod to another, with the constraint that only one disk can be moved at a time and a larger disk cannot be placed on top of a smaller disk. The solution demonstrates the elegance of recursion for problem-solving.

**Example**:

1 2 3 4 5 6 7 8 9 10 |
def hanoi(n, source, target, auxiliary): if n == 1: print(f"Move disk 1 from {source} to {target}") return hanoi(n-1, source, auxiliary, target) print(f"Move disk {n} from {source} to {target}") hanoi(n-1, auxiliary, target, source) # Solving Tower of Hanoi for 3 disks hanoi(3, 'A', 'C', 'B') |

### Fractals

Fractals are complex geometric shapes that can be split into parts, each of which is a reduced-scale copy of the whole. This property makes them ideal candidates for recursive generation. A common example is the Sierpiński triangle.

**Example with Turtle Graphics for Sierpiński Triangle**:

This example requires the `turtle`

module, which is part of the standard Python library and provides a graphical environment for drawing shapes.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
import turtle def draw_triangle(points, color, my_turtle): my_turtle.fillcolor(color) my_turtle.up() my_turtle.goto(points[0][0], points[0][1]) my_turtle.down() my_turtle.begin_fill() my_turtle.goto(points[1][0], points[1][1]) my_turtle.goto(points[2][0], points[2][1]) my_turtle.goto(points[0][0], points[0][1]) my_turtle.end_fill() def sierpinski(points, degree, my_turtle): colormap = ['blue', 'red', 'green', 'white', 'yellow', 'violet', 'orange'] draw_triangle(points, colormap[degree], my_turtle) if degree > 0: sierpinski([points[0], get_mid(points[0], points[1]), get_mid(points[0], points[2])], degree-1, my_turtle) sierpinski([points[1], get_mid(points[0], points[1]), get_mid(points[1], points[2])], degree-1, my_turtle) sierpinski([points[2], get_mid(points[2], points[1]), get_mid(points[0], points[2])], degree-1, my_turtle) def get_mid(p1, p2): return ((p1[0]+p2[0]) / 2, (p1[1]+p2[1]) / 2) my_turtle = turtle.Turtle() my_win = turtle.Screen() my_points = [[-100, -50], [0, 100], [100, -50]] sierpinski(my_points, 3, my_turtle) my_win.exitonclick() |

This script draws a Sierpiński triangle of degree 3. The `sierpinski`

function recursively draws smaller triangles within each larger triangle, creating a fractal pattern.

### Recursion Depth Limit

Python has a limit on the depth of recursion to prevent a stack overflow. However, this limit can be adjusted using the `sys.setrecursionlimit()`

function.

1 2 |
import sys sys.setrecursionlimit(2000) # Be cautious with this |

### The `functools.lru_cache`

decorator in Python

The `functools.lru_cache`

decorator in Python is a powerful feature that can significantly optimize recursive functions by caching their results. This is particularly useful for functions that are called repeatedly with the same arguments, as it prevents the re-computation of results that have already been calculated. Here’s how to use `lru_cache`

with recursion, along with some examples.

### Basic Usage of `lru_cache`

First, you need to import `lru_cache`

from the `functools`

module.

**Example: Fibonacci Sequence with lru_cache**

Without caching, the recursive Fibonacci function recalculates values many times, leading to an exponential time complexity.

1 2 3 4 5 6 7 8 9 10 |
from functools import lru_cache @lru_cache(maxsize=None) # Cache all results def fibonacci(n): if n <= 1: return n else: return fibonacci(n-1) + fibonacci(n-2) print(fibonacci(30)) # This computation is now much faster with caching. |

### Example: Computing Factorials with `lru_cache`

Similar to the Fibonacci sequence, computing factorials can also benefit from caching since the calculation of `n!`

(n factorial) requires the value of `(n-1)!`

, `(n-2)!`

, and so on.

1 2 3 4 5 6 7 8 9 10 |
from functools import lru_cache @lru_cache(maxsize=None) def factorial(n): if n == 0: return 1 else: return n * factorial(n-1) print(factorial(5)) # Output: 120 |

### Example: Path Counting in a Grid with `lru_cache`

Consider a problem where you need to count all possible paths from the top-left corner to the bottom-right corner of a 2D grid, and you can only move right or down. Caching is beneficial here due to overlapping subproblems.

1 2 3 4 5 6 7 8 9 |
from functools import lru_cache @lru_cache(maxsize=None) def count_paths(rows, cols): if rows == 1 or cols == 1: return 1 return count_paths(rows-1, cols) + count_paths(rows, cols-1) print(count_paths(5, 5)) # Output: 70 |

### Managing `lru_cache`

`lru_cache`

provides a few methods to manage the cache, such as `cache_info()`

which returns information about the cache’s hits, misses, maxsize, and current size, and `cache_clear()`

which can be used to clear the cache.

**Example: Using cache_info() and cache_clear()**

1 2 3 4 |
print(fibonacci.cache_info()) # Get cache statistics fibonacci.cache_clear() # Clear cache print(fibonacci.cache_info()) # Cache is now empty |

Using `lru_cache`

with recursion not only optimizes your program’s performance by avoiding redundant calculations but also demonstrates an efficient use of memory and processing power, especially for computationally intensive tasks. Remember, while `lru_cache`

is a powerful tool, it’s most effective when used in scenarios with high repetition of function calls with the same parameters.

Recursion is a fundamental concept in computer science, offering elegant solutions to complex problems. However, it’s important to use recursion judiciously, as it can lead to high memory usage and stack overflow errors if not properly managed. Understanding when and how to apply recursion will significantly enhance your problem-solving skills in Python.