Recursion is a powerful programming technique that breaks complex problems into simpler subproblems. By calling a function within itself, recursion solves each subproblem until reaching a base case , then combines the results to solve the original problem.
Writing recursive functions requires careful consideration of base cases and recursive cases. Tracing recursive algorithm execution helps understand how the function works, while optimization techniques like memoization can improve performance. Recursion is a valuable tool for solving complex problems efficiently.
Recursion Fundamentals
Recursion for problem simplification
Top images from around the web for Recursion for problem simplification CS 201: Lecture 20: Recursion View original
Is this image relevant?
CS 201: Lecture 20: Recursion View original
Is this image relevant?
1 of 3
Top images from around the web for Recursion for problem simplification CS 201: Lecture 20: Recursion View original
Is this image relevant?
CS 201: Lecture 20: Recursion View original
Is this image relevant?
1 of 3
Recursion breaks down complex problems into simpler subproblems
Divides original problem into smaller, more manageable parts
Solves each subproblem recursively by calling the same function
Combines solutions of subproblems to solve the original problem
Recursive functions consist of two main components:
Base case: simple, non-recursive condition that terminates recursion (empty list, zero, one)
Recursive case: condition that calls the function itself with a simpler input (smaller list, reduced number)
Calculating factorial of a number n n n recursively (4!, 5!)
Factorial of n n n defined as n ! = n × ( n − 1 ) × ( n − 2 ) × . . . × 2 × 1 n! = n \times (n-1) \times (n-2) \times ... \times 2 \times 1 n ! = n × ( n − 1 ) × ( n − 2 ) × ... × 2 × 1
Base case: n = 0 n = 0 n = 0 or n = 1 n = 1 n = 1 , factorial is defined as 1
Recursive case: breaks down problem into simpler version by calculating n ! = n × ( n − 1 ) ! n! = n \times (n-1)! n ! = n × ( n − 1 )!
Recursion often employs a divide and conquer strategy to solve problems
Writing recursive functions
Recursive functions must have a base case to avoid infinite recursion
Base case: condition that causes function to return without further recursive calls
Typically the simplest possible input for the function (empty list, zero, one)
Recursive case: function calls itself with a modified input
Modified input should move closer to base case with each recursive call (smaller list, reduced number)
Ensures function will eventually reach base case and terminate
Recursive function to calculate sum of numbers from 1 to n n n
[ def ] ( https : // www . fiveableKeyTerm : def ) sum_recursive ( n ) :
if n == 1 :
return 1
else :
return n + sum_recursive ( n - 1 )
Tail recursion is a specific form where the recursive call is the last operation in the function
Tracing recursive algorithm execution
Tracing execution helps understand how recursive function works
Keeps track of each function call and corresponding return value
Function calls represented in a call stack , most recent call at the top
When recursive function called, added to top of call stack
If base case met, function returns value and is removed from stack
If recursive case met, new function call added to top of stack
Return values passed back through call stack as each function call completes
Tracing execution of recursive factorial function for n = 4 n = 4 n = 4
factorial(4)
├── 4 * factorial(3)
├── 3 * factorial(2)
├── 2 * factorial(1)
├── 1 (base case)
├── 2 * 1 = 2
├── 3 * 2 = 6
├── 4 * 6 = 24
Recursion can lead to stack overflow errors if the call stack becomes too large
Memoization can improve performance by storing results of expensive function calls
Iteration is often an alternative to recursion, potentially offering better performance in some cases