AI Hints
Home›DSA in Python Tutorial›Recursion Practice
DSA in Python · Lesson 43 of 132

Recursion Practice

Sum, power and digits.

⏱ 2 min read▶ Video at 49:39🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

The secret to writing recursion is to trust it. Ask two questions. What's the smallest version, that I can answer directly? And how can I solve a big version, if someone solved a slightly smaller one for me? Let's practise with three small problems.

Recursion Practice
From the video: Recursion Practice
  • Trust the recursion
  • What's the smallest case?
  • How does smaller help?

Three recursive functions

The sum of a list is the first item, plus the sum of the rest. An empty list sums to zero. Power of a number is the number, times the power one smaller. Anything to the power zero is one. And the sum of digits is the last digit, plus the sum of the digits that are left. Run it.

practice.pypython
def total(nums):
    if not nums:
        return 0
    return nums[0] + total(nums[1:])

def power(x, n):
    if n == 0:
        return 1
    return x * power(x, n - 1)

def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)

print(total([4, 2, 7]), power(2, 10), digit_sum(2026))
Output
13 1024 10

The recipe

Every recursive function follows the same recipe. First, handle the base case, and return the answer directly. Second, make the problem smaller. Third, call yourself on the smaller problem. Fourth, combine that result into your answer. If you can describe those four steps, the code almost writes itself.

keyvalue
1. Base caseanswer directly
2. Shrinkmake it smaller
3. Recursecall yourself
4. Combinebuild your answer

Summary

Base case, shrink, recurse, combine. With that recipe, recursion becomes much less mysterious. Next, a way to make slow recursion incredibly fast. Memoization.

Key takeaways
  • Trust it
  • Base case, shrink, recurse, combine
  • Practise small problems
Next up: Memoization — remember answers