Recursive step
- Algorithms course
- Beginner
- Lesson 39/80
- 4 min
Break the problem into a smaller same-shape problem.
Recursion vs loop
Many recursion problems can also be solved with a loop. Recursion may be more readable but each call uses stack space.
Loops generally use less memory. Recursion makes it easier to think by dividing the problem.
Call stack
Each recursive call adds a frame to the stack. When the base case is reached, calls unwind and each frame returns its result.
Very deep recursion can cause stack overflow. That is why loops are preferred for very large inputs.
Practice Array length (recursive)
Write length_recursive(arr). If empty return 0, else 1 + length_recursive(arr[1:]). Print 4 with print(length_recursive([4, 5, 6, 7])).
Starter code
def length_recursive(arr):
# Compute lengthSample solution
def length_recursive(arr):
# Compute length
if len(arr) == 0:
return 0
return 1 + length_recursive(arr[1:])
print(length_recursive([4, 5, 6, 7]))Expected output
4
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Recursive step: match the terms
| Term | Meaning |
|---|---|
Recursion |
Uses stack |
Loop |
Less memory |
Stack overflow |
Too deep |
Base case |
Stops |
2 What does recursion use that loops do not?
- Stack space Correct answer
- Loop
- Hash table
- Tree
Explanation: Recursion uses stack space.
3 Stack overflow
Very deep recursion causes ____.Very deep recursion causes stack overflow.Explanation: stack overflow is right.