Recursion on lists and strings in Python

Why it matters

Most recursion questions in interviews start from a list or a string. The list might hold prices, scores or readings. The string might hold a word, a sentence or a file name. The skill you need is the same in every case: decide what "smaller" means, handle one piece yourself, and trust the recursive call to handle the rest. If you can do that for a list and a string, you can do it for a tree, a graph or a list of files.

This lesson builds on the first one. You already know the base case, the recursive case and the call stack. Here you will apply them to data that has an order: positions 0, 1, 2 and so on. You will also meet a problem that recursion can solve correctly but very slowly, and you will learn the fix.

The idea from the first principle

A list in Python is a row of boxes that can hold values. A list can mix types, but in this lesson each list holds whole numbers. The expression [4, 7, 1, 8] creates four boxes. Box 0 holds 4, box 1 holds 7, box 2 holds 1 and box 3 holds 8. The number of a box is its index. The number of boxes is the length, which len(data) returns, here 4.

A string is also a row of characters. The word level is five characters: l, e, v, e, l. The expression s[2] returns the character at index 2, which is v. Python has no separate character type. A single character is a string of length 1, so type("s") is str. The indexes of a string start at 0 and go up to len(s) - 1, the same rule as lists.

Think about a line of people standing in a queue. Suppose you want to know how many people in the line have a red bag. You can ask the first person whether they have a red bag, then pass the question down the line to the rest of the queue. Each person answers for themselves and asks the next person for the count of the rest. The last person has nobody behind them, so they answer for themselves only. That is the whole pattern. For a list, the queue is the index: person number i is arr[i], and the rest of the queue starts at i + 1.

This gives a simple three-step habit for lists and strings:

1. Write the base case. It is usually an empty range, or a range with one element.
2. Handle one element yourself, the one at the current index.
3. Ask the recursive call to handle the rest, starting one position later, and combine the two answers.

Notice that you never copy the list. You pass the same list every time, along with a changing index. Copying the list on each call would make a simple O(n) problem cost O(n squared), which is a common beginner mistake that you will see again in the Common mistakes section.

Sum of a list

Start with the simplest useful problem: add up every value in a list. The rule from the queue example applies directly. The sum from index i onward is the value at i, plus the sum from index i + 1 onward. When i reaches the length of the list, there is nothing left, and the sum is 0.

Press Run. The output is:

20
0
1

The function takes two parameters: the list, and the index i where the current call starts. The base case is i == len(arr), which is one past the last valid index. That is the right stopping point, because the last valid index is len(arr) - 1, and the call for that index still needs to add its own value. Many beginners write if i == len(arr) - 1 as the base case and return 0 there. That skips the last element, so the total is wrong. Test your base case with the smallest list you can think of: an empty list, which should return 0.

The third line shows that negative numbers need no special handling. Addition works the same for them, so the sum of -3, 5 and -1 is 1.

Trace the calls for [4, 7, 1, 8] starting at index 0. Each row shows a call and what it will return:

total(arr, 0) = arr[0] + total(arr, 1) = 4 + ...
total(arr, 1) = arr[1] + total(arr, 2) = 7 + ...
total(arr, 2) = arr[2] + total(arr, 3) = 1 + ...
total(arr, 3) = arr[3] + total(arr, 4) = 8 + ...
total(arr, 4) = 0, because 4 equals len(arr)

Now the return values travel back up: 8 + 0 = 8, then 1 + 8 = 9, then 7 + 9 = 16, and finally 4 + 16 = 20.

Each call uses one stack frame, so the stack depth is the length of the list. The time is O(n), because each element is visited once. Compare this with a loop, which would also be O(n) time but O(1) extra space. For a list of a few hundred values the recursion is fine. For a list of several thousand values Python stops it with a RecursionError, and you will test that limit in a later section.

For a plain sum, Python has a built-in sum(arr) that is faster and has no depth limit. The recursive version is still worth writing, because it teaches the pattern that you will use on trees and nested data.

Maximum of a list

The maximum of a list is the largest value. The same queue pattern works: the largest value is the bigger of the first value and the largest of the rest. Python has a built-in max(a, b) that returns the larger of two values, so you do not write the comparison yourself.

This version uses a different base case. Instead of stopping one past the end, it stops at the last index, where the answer is just that value:

Press Run. The output is:

8
-5
9

Both base cases are valid, but they fit different problems. The sum needs an empty answer for an empty tail, so it stops one past the end. The maximum has no sensible answer for an empty tail, so it stops at the last element. This means largest fails on an empty list, because arr[0] does not exist. Python then raises an IndexError:

IndexError: list index out of range

A careful function checks for an empty list before the call, and decides what the answer should be. This is the kind of detail an interviewer checks, so mention it when you explain your solution.

The cost is the same as the sum: one call per element, O(n) time, and O(n) stack depth.

Palindromes: two pointers moving inward

A palindrome reads the same forwards and backwards. The words level, noon and a are palindromes. The word lever is not, because its first letter l does not match its last letter r.

For a string, the queue idea changes slightly. Instead of one index moving forward, you use two indexes. The left index starts at the first letter and moves right. The right index starts at the last letter and moves left. At each step you compare the two letters. If they differ, the word is not a palindrome. If they match, you move both indexes inward and check the next pair. The two pointers meet in the middle, and then there is nothing left to check.

Here is the picture for racecar, which is a palindrome. Each row is one call, and the two letters it compares are the ones that the left and right pointers point at:

call 1: left = 0, right = 6   r and r match
call 2: left = 1, right = 5   a and a match
call 3: left = 2, right = 4   c and c match
call 4: left = 3, right = 3   pointers meet on the middle letter, returns True

Watch for two things. The pointers always move toward each other, never apart. And the check stops as soon as the pointers cross or meet, because a single letter or an empty middle is always a palindrome.

Here is the recursive version. The function receives the string, a left index and a right index:

Press Run. The output is:

'level' True
'lever' False
'abba' True
'racecar' True
'racecaz' False
'' True

The repr(word) call shows each word inside quotes, so you can see the empty string as ''. The last line passes len(word) - 1, which is -1 for the empty string. The base case left >= right is true at once, so the empty string is a palindrome.

Read the base case carefully. The check is left >= right, not left == right. The difference matters for words of even length. The word abba has four letters. Its pointers go from 0 and 3, then 1 and 2, and then 2 and 1. At that point left has passed right. The check left >= right catches this and returns True. A check of left == right would miss it, as the Debugging walkthrough shows.

The cost is O(n) time, because each pair of letters is compared once, and O(n/2) stack depth, which is O(n). The function never creates a new string, so the space used for the letters is the one string you were given.

Reversing a string

Reversing a string means producing the letters in the opposite order. The recursive idea is this: the reverse of a string is the reverse of everything after the first letter, followed by the first letter. For abc, the reverse of bc is cb, and adding a at the end gives cba.

This function builds the answer on the way out, so the work happens after each recursive call returns. It uses slicing. The expression s[1:] returns the part of the string from index 1 to the end:

Press Run. The output is:

cba
egrof
[]

Trace reverse("abc"). It calls reverse("bc") and then adds "a". reverse("bc") calls reverse("c"), which returns "c" because its length is 1. Then reverse("bc") adds "b" to get "cb". Finally reverse("abc") adds "a" and returns "cba". The function is correct, but it is slow. Each slice s[1:] copies the rest of the string into a new string, which costs time proportional to its length. Adding all those copies gives O(n squared) time. The idea is clear, and that is the point of the example, but the code you would write in real Python is O(n):

result = s[::-1]

The slice s[::-1] means "from start to end, stepping by -1", which walks the string backwards and builds the reversed copy in one pass. Use it in real code. The point to remember is that a recursive idea can be correct and still be a poor choice for production code. Say so in an interview, and then offer the better version.

Counting a character with an index

Counting how many times a letter appears in a string is a clean example of an index-based function. Pass the current index as a parameter, and add 1 for each match:

Press Run. The output is:

4
4
0

The word mississippi has four s letters and four i letters. The empty string returns 0 at once, because i == len(s) is true when i is 0.

The line here = 1 if s[i] == c else 0 uses Python's conditional expression. It reads: use the value before if when the test after if is true, otherwise use the value after else. It is a short way to write a small if and else on one line. You can always write it as a full if statement instead. Interviewers do not mind either form, as long as the logic is clear.

Python has no separate type for one character. The letter "s" in double quotes is a str of length 1, the same type as a whole word. That is why count_char can compare with == and does not need a special character type. In Python, a mix-up shows up as a plain False from the comparison rather than an error, so check that the value you pass really has length 1.

Repeated work and memoization

Now the warning sign from the first lesson comes back. The plain Fibonacci function makes two calls for each value, and the calls overlap. The call fib(3) is made inside fib(5) and again inside fib(4). The same answer is worked out over and over.

The fix is called memoization. The word comes from "memo", a note to yourself. The idea is simple: when a call finishes, write its answer in a table. Before a call does any work, look in the table. If the answer is already there, return it straight away. Each value of n is then worked out once, and the rest of the calls are cheap lookups.

Python uses a dictionary for the table. A dictionary is a set of key and value pairs, written with curly braces, such as {2: 1}. The key is the input, and the value is the answer. The test n in memo asks whether a key is already in the table.

Press Run. The output is:

55
12586269025
2880067194370816120

The table is memo, a dictionary that starts empty. The base case n <= 1 is checked first, so the table only ever holds answers for n of 2 or more. The table grows as the calls run, so it holds one entry for each n that was worked out. Python integers never overflow, so fib(90) is exact, which would not be true for a fixed-size integer type in some other languages.

Trace fib(5) with the table. The call goes to fib(4), which goes to fib(3), and so on down to fib(1), which returns 1. Then fib(2) computes fib(1) + fib(0), which is 1, and stores memo[2] = 1. When fib(3) asks for fib(2), the answer is there. Each value is now computed once, and each call makes two calls at most, so the total work is O(n) instead of O(2^n).

Python has a shorter way to get the same effect. The functools module has a decorator called cache. A decorator is a line that starts with @ and changes the function below it. Here @cache wraps fib in a table, so you do not write the lookups yourself:

Press Run. The output is:

2880067194370816120
CacheInfo(hits=88, misses=91, maxsize=None, currsize=91)

The cache_info() line counts what happened. There were 91 misses, one for each n from 0 to 90, where the function did real work. There were 88 hits, where an answer came straight from the table. The numbers show that each value was computed once. Use @cache in your own code when the inputs are simple and hashable, which means numbers, strings and tuples. A list cannot be a key in a dictionary, so @cache does not work with list arguments.

The cost is O(n) time and O(n) space. The table uses O(n) memory, and the stack depth is also O(n). You will meet the same idea under a new name, dynamic programming, in the course module on that topic. The core habit is the same: store answers that repeat.

How deep can a recursion go in Python

Every call uses a stack frame, and Python limits the depth. The limit is 1000 by default, as the first lesson showed. A list sum with one call per element has a depth equal to the length of the list. So how long a list can you sum recursively? A quick test answers the question for the Python you are running. The program below fills lists of two sizes and reports whether the recursive sum fails:

Press Run. The output is:

500 elements overflow: False
5000 elements overflow: True

The exact limit depends on the Python version and on how many frames are already in use, so your numbers may differ, but the lesson holds: a recursion with one call per element works for hundreds of elements and fails for thousands. For real work with long lists, use a loop or the built-in sum. Use recursion when the input is small, or when the structure of the problem is naturally recursive, such as a tree.

Common mistakes

Wrong base case index. A base case that checks the value instead of the position can read past the end of the list. Here is a function that tries to stop at zeros, but checks the wrong thing:

def total_bad(arr: list[int], i: int) -> int:
    if arr[i] == 0:  # checks the value, not the position
        return 0
    return arr[i] + total_bad(arr, i + 1)

Called on [4, 7, 1, 8], it fails when the index reaches 4, because there is no arr[4]. The real error is this:

Traceback (most recent call last):
  File "total_bad.py", line 8, in <module>
    print(total_bad([4, 7, 1, 8], 0))
          ~~~~~~~~~^^^^^^^^^^^^^^^^^
  File "total_bad.py", line 4, in total_bad
    return arr[i] + total_bad(arr, i + 1)
                    ~~~~~~~~~^^^^^^^^^^^^
  File "total_bad.py", line 4, in total_bad
    return arr[i] + total_bad(arr, i + 1)
                    ~~~~~~~~~^^^^^^^^^^^^
  File "total_bad.py", line 4, in total_bad
    return arr[i] + total_bad(arr, i + 1)
                    ~~~~~~~~~^^^^^^^^^^^^
  [Previous line repeated 1 more time]
  File "total_bad.py", line 2, in total_bad
    if arr[i] == 0:  # checks the value, not the position
       ~~~^^^
IndexError: list index out of range

The message says list index out of range, but it does not say which index failed. The traceback helps: the last frame points at the line if arr[i] == 0, and the repeated frames show that the calls went deeper and deeper. The fix is to check the position, i == len(arr), and to stop there.

Negative indexes wrap around. Python has one feature that other languages do not. A negative index counts from the end, so arr[-1] is the last element and s[-1] is the last letter. This is useful, but it can hide a bug. If the base case lets an index drop to -1, the function may keep working on the wrong data and never raise an error. Check that your indexes stay between 0 and len - 1, or that the base case stops them before they go negative.

Forgetting to move the index. Calling total(arr, i) instead of total(arr, i + 1) never shrinks the problem. The calls pile up on the same index, and Python stops the program with a RecursionError.

Copying the list on every call. Passing arr[1:] on each step looks neat, but each slice copies the list, and the total becomes O(n squared). Pass the index instead.

Assuming an empty list is safe. The maximum function above fails on an empty list. Check len(arr) == 0 before calling it, and decide what the answer should be.

Using is to compare values. The is operator checks whether two names point to the same object in memory. The == operator checks whether the values are equal. For numbers and strings, use ==. Using is can work by chance for small values, and then fail for others, so do not rely on it.

Debugging walkthrough

Here is a palindrome function with one small mistake. It is written with == in the base case:

def is_palindrome(s: str, left: int, right: int) -> bool:
    if left == right:  # bug: should be left >= right
        return True
    if s[left] != s[right]:
        return False
    return is_palindrome(s, left + 1, right - 1)

Call it on abba, with the indexes 0 and 3. Use the debugging method from the first lesson. Name the answer first: abba is a palindrome, so the function should return True. Find the smallest input where the function fails. The word abba is the smallest one of even length that the check left == right does not handle, because the pointers jump over each other and never become equal.

Trace it on paper. The call (0, 3) compares a with a, which match. The call (1, 2) compares b with b, which match. The call (2, 1) has left equal to 2 and right equal to 1, so left == right is false and it does not stop. It compares s[2], which is b, with s[1], which is b, and they match. The call (3, 0) compares a with a and matches. The call (4, -1) reads s[4], which is past the end of a string of length 4. Running it gives the real error:

Traceback (most recent call last):
  File "palindrome.py", line 9, in <module>
    print(is_palindrome("abba", 0, 3))
          ~~~~~~~~~~~~~^^^^^^^^^^^^^^
  File "palindrome.py", line 6, in is_palindrome
    return is_palindrome(s, left + 1, right - 1)
  File "palindrome.py", line 6, in is_palindrome
    return is_palindrome(s, left + 1, right - 1)
  File "palindrome.py", line 6, in is_palindrome
    return is_palindrome(s, left + 1, right - 1)
  [Previous line repeated 1 more time]
  File "palindrome.py", line 4, in is_palindrome
    if s[left] != s[right]:
       ~^^^^^^
IndexError: string index out of range

The last frame points at s[left], and the message says the string index is out of range. The fix is the base case left >= right, which stops as soon as the pointers cross. This is a good example of a bug that only shows on some inputs. The word level, with an odd number of letters, works with the wrong check, because the pointers do meet in the middle. The even-length word fails, and that is why you test with both kinds of input.

Variations and edge cases

Real palindrome questions often ignore spaces, punctuation and case. A phrase like A man, a plan, a canal: Panama counts as a palindrome in many interviews. The recursive function stays the same, but the two pointers skip characters that are not letters, and they compare letters in lower case. The skipping is a small loop inside the recursion, or a separate helper that moves a pointer to the next letter. Here is the case-insensitive version. It lower-cases each letter before the comparison:

The output is:

True
False

Plan the skipping rules before you code. Ask the interviewer which characters should be ignored.

Lists can also be split into two halves. The sum of the whole list equals the sum of the left half plus the sum of the right half. That idea is the start of divide and conquer, which the next module covers. For now, notice that it has two recursive calls, which is what makes it useful and also what makes it easy to lose track of the work.

When a list problem can be solved with a loop or a built-in in O(n) time, the loop or built-in is usually the better choice in production. Recursion shines when the data itself is recursive, such as a tree whose nodes have children, or a nested list. Learn the loop version too, and be ready to explain why you chose one over the other.

Interview and real-world uses

Interviewers often ask "write a recursive function for this list problem" and then ask for the time cost and the stack depth. A strong answer names the base case, moves the index, combines the answers, and states O(n) time and O(n) stack space. If the problem has repeated subproblems, the strong answer adds memoization, with @cache or a dictionary, and gives the new time cost, O(n) instead of O(2^n).

In real software, index-based recursion appears in parsers that read text one character at a time, in searches that check whether a text matches a pattern, and in validators that test whether a sequence is symmetric or well formed. Parsers often read very long files, so they use loops or explicit stacks instead of deep recursion. The habit of moving an index is still the same.

Tracing a longer palindrome step by step

The short words in the earlier examples hide how the pointers move, so trace a longer one. Take racecar, which has seven letters. The left index starts at 0 and the right index starts at 6. The table below shows each call, the two letters it compares, and what it returns:

Read the table from the top. Calls 1 to 3 each compare two equal letters and pass the work on. Call 4 is the base case, because the pointers meet on the middle letter, e. The middle letter of an odd-length word always meets itself, and that is why the check is left >= right and not a comparison of letters. The final answer returns from call 4 up through calls 3, 2 and 1, and each of them returns the same value, True.

Now change one letter and trace again. If the word is racecaz, call 1 compares r with z, which differ, so call 1 returns False at once. Notice that the function stopped at the outermost pair, without looking at the inside. A palindrome check can stop at the first mismatch, which is why a non-palindrome is usually rejected quickly.

Reading a list from the end

Our examples moved the index up from 0. You can also move it down from the last position. The answer is the same, but the base case changes, because the calls stop when the index falls below 0 instead of reaching the length. Here is the sum written that way:

The output is:

20
0

Call it with len(arr) - 1 as the starting index. The first call uses the last index, not the first one. The base case i < 0 is the mirror of i == len(arr). Both versions do one call per element, so both cost O(n) time and O(n) stack space. Choosing a direction is a matter of taste, but you must make the starting index and the base case agree. A common bug is to start at len(arr), which reads past the end of the list on the first call. Here is that bug on a two-element list:

The output is:

Traceback (most recent call last):
  File "wrong_start.py", line 7, in <module>
    print(sum_from_start_wrong([4, 7], 2))
          ~~~~~~~~~~~~~~~~~~~~^^^^^^^^^^^
  File "wrong_start.py", line 4, in sum_from_start_wrong
    return arr[i] + sum_from_start_wrong(arr, i - 1)
           ~~~^^^
IndexError: list index out of range

The first call reads arr[2], which does not exist for a two-element list. Test both versions with an empty list, which is the simplest way to see whether the base case agrees with the starting index.

The mirror version matters in one practical case. If a problem asks for the last matching item first, moving down finds it without extra work. The same goes for building a result from the end of a string, where the answer is built as the calls return and the characters come out in reverse order.

Reversing a list in place

Reversing a string gives you a new string. Reversing a list can change the list itself, which is called reversing in place. The recursive idea is the palindrome check with a swap: swap the two ends, then reverse the inside.

The output is:

[4, 3, 2, 1]

The line arr[left], arr[right] = arr[right], arr[left] swaps two values in one step. Python builds the right-hand pair first, so no temporary variable is needed. The function returns None, because the list was changed in place and there is nothing new to return.

Walking through a palindrome question in an interview

Interviewers often ask whether a word is a palindrome, then add a twist. A good answer follows the same order each time, and that order matters more than a fast first answer.

First, restate the question. Ask whether the check should ignore case, spaces and punctuation, and whether an empty string counts. Second, give examples. Name one palindrome of odd length, such as level, one of even length, such as abba, one that fails at the first pair, such as lever, and the empty string. Third, name the approach: two pointers that move toward the middle. Fourth, write the code, starting with the base case. Fifth, test the code by hand on the examples, and say what each result should be. Sixth, state the cost: O(n) time, one comparison per pair, and O(n) stack space for the calls.

The interviewer will often push on the cost. A strong answer then says that the stack space can be made O(1) with a loop, because two index variables are enough. Saying that shows you know the recursion is optional here, which is the point the interviewer is testing. If you are asked to avoid recursion, write the loop with while left < right: and explain that it does the same comparisons in the same order.

A checklist for list and string recursion

Use this checklist when you write any recursive function over a list or a string. Each item is a question you should be able to answer before you run the code.

• Which index does the first call start from, and does the base case match that start?
• Does every call move the index, so that the base case is always reachable?
• Is the base case the smallest input the function can receive, including the empty list?
• Does the function pass the same list or string, and never a copy, so the cost stays O(n)?
• If the function returns a maximum or minimum, what does it return for an empty input?
• What is the stack depth, and could a large input hit the recursion limit?

If you can answer all six, the function is probably right. If one answer is unclear, trace the smallest input you can think of before you write more code.

Questions learners ask about list recursion

Why not just use a loop or sum? For plain sums and maximums, a loop or the built-in is the better production choice. It uses O(1) extra space and has no depth limit. The recursive version is still worth learning, because it is the same shape as the recursion on trees and nested lists, where a loop is much harder to write.

Why pass the index instead of a shorter list? Passing an index lets every call look at the same list without copying it. A slice of the tail costs time proportional to its length on every call, which turns an O(n) function into O(n squared). The index is a single number, so passing it costs almost nothing.

Do negative numbers change the sum? No. Addition works the same for negative values, so total returns the right result for [-3, 5, -1], which is 1. Negative numbers do matter for the maximum. The function for [-5] in this lesson returns -5, because the single element is the answer. A function that starts from 0 would be wrong for a list of all negative values.

Practice

Exercise 1 (easy). Write largest(arr, i) that returns the largest element, using the base case at the last index. Test it on [3, 9, 2], which should return 9.

Show the answer

def largest(arr: list[int], i: int) -> int:
    if i == len(arr) - 1:
        return arr[i]
    return max(arr[i], largest(arr, i + 1))
 
 
print(largest([3, 9, 2], 0))  # 9

The base case returns the last element. Each call compares its own element with the largest of the rest. For [3, 9, 2] the result is max(3, max(9, 2)), which is 9.

Exercise 2 (easy). Write count_char(s, c, i) that counts how many times c appears in s. Test it on banana with the letter a, which should give 3.

Show the answer

def count_char(s: str, c: str, i: int) -> int:
    if i == len(s):
        return 0
    here = 1 if s[i] == c else 0
    return here + count_char(s, c, i + 1)
 
 
print(count_char("banana", "a", 0))  # 3

The function is the same as the one in this lesson. For banana the letter a appears at positions 1, 3 and 5, so the answer is 3.

Exercise 3 (easy). Before running it, predict what total([], 0) returns, and what the function would do on an empty list if the base case were i == len(arr) - 1 returning 0. Then run both versions to check.

Show the answer

The correct version returns 0, because i == len(arr) is true at once. The wrong version reads arr[0] for the empty list, which does not exist, so it raises IndexError: list index out of range. For a non-empty list the wrong version skips the last element, so the total is too small by that element's value.

Exercise 4 (medium). Write is_palindrome(s) that takes only one argument and calls a two-index helper, so that a caller passes just the string. Test it on noon and north.

Show the answer

def is_palindrome(s: str) -> bool:
    return _check(s, 0, len(s) - 1)
 
 
def _check(s: str, left: int, right: int) -> bool:
    if left >= right:
        return True
    if s[left] != s[right]:
        return False
    return _check(s, left + 1, right - 1)
 
 
print(is_palindrome("noon"))   # True
print(is_palindrome("north"))  # False

The public function hides the two indexes from the caller. The leading underscore in _check is a Python convention that says the helper is for internal use. noon returns True, and north returns False, because n and h differ at the first step.

Exercise 5 (medium). Write a recursive function has_duplicate(arr, i) that returns True when some value appears more than once, comparing arr[i] with the rest of the list. Hint: a single element cannot repeat. Think about the cost, and say whether this function is O(n) or O(n squared).

Show the answer

def has_duplicate(arr: list[int], i: int) -> bool:
    if i >= len(arr):
        return False
    if contains(arr, arr[i], i + 1):
        return True
    return has_duplicate(arr, i + 1)
 
 
def contains(arr: list[int], value: int, start: int) -> bool:
    if start >= len(arr):
        return False
    return arr[start] == value or contains(arr, value, start + 1)
 
 
print(has_duplicate([3, 1, 4, 1, 5], 0))  # True
print(has_duplicate([1, 2, 3], 0))        # False

Each element is compared with every later element, so the total work is O(n squared). This is correct but slow. A set would bring the cost down to O(n), because checking membership in a set takes about the same time whatever its size. You will meet sets in later modules. The Python shortcut is len(set(arr)) < len(arr).

Exercise 6 (medium). Write reverse_in_place(arr, left, right) that reverses a list by swapping the two ends and recursing inward. Test it on [1, 2, 3, 4], which should become [4, 3, 2, 1].

Show the answer

def reverse_in_place(arr: list[int], left: int, right: int) -> None:
    if left >= right:
        return
    arr[left], arr[right] = arr[right], arr[left]
    reverse_in_place(arr, left + 1, right - 1)
 
 
data = [1, 2, 3, 4]
reverse_in_place(data, 0, len(data) - 1)
print(data)  # [4, 3, 2, 1]

Each swap puts two values in their final places, and the base case stops when the pointers cross. The list is changed in place, so the function returns None.

Exercise 7 (medium). Modify the palindrome check so that it ignores case, so that Level counts as a palindrome. Hint: convert the characters to lower case with .lower() before comparing them.

Show the answer

def is_palindrome_ignore_case(s: str, left: int, right: int) -> bool:
    if left >= right:
        return True
    if s[left].lower() != s[right].lower():
        return False
    return is_palindrome_ignore_case(s, left + 1, right - 1)
 
 
print(is_palindrome_ignore_case("Level", 0, 4))  # True

The only change is the comparison. Lower-casing each letter before comparing means L and l match. The base case and the index movement are the same as before.

Exercise 8 (hard). Count the number of ways to climb n stairs when you may take one or two steps at a time, using @cache. Write ways(n) with the base cases ways(0) = 1 and ways(1) = 1, and the rule ways(n) = ways(n - 1) + ways(n - 2). Check that ways(5) is 8. Hint: this is the Fibonacci pattern with different starting values.

Show the answer

from functools import cache
 
 
@cache
def ways(n: int) -> int:
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)
 
 
print(ways(5))  # 8

For 5 stairs the values go 1, 1, 2, 3, 5, 8, so ways(5) is 8. The cache turns the repeated calls into lookups. The base cases differ from Fibonacci, because there is 1 way to climb 0 stairs and 1 way to climb 1 stair.

Exercise 9 (hard). Write a recursive function that checks whether a string of round brackets is balanced, such as (()()) (balanced) or (() (not balanced). Hint: track a count of open brackets as an extra parameter, and return False if the count goes negative or is not zero at the end.

Show the answer

def balanced(s: str, i: int, open_count: int) -> bool:
    if open_count < 0:
        return False
    if i == len(s):
        return open_count == 0
    if s[i] == "(":
        return balanced(s, i + 1, open_count + 1)
    return balanced(s, i + 1, open_count - 1)
 
 
print(balanced("(()())", 0, 0))  # True
print(balanced("(()", 0, 0))     # False

An opening bracket adds one to open_count. A closing bracket takes one away. If the count ever goes negative, a closing bracket came before its opening bracket, so the answer is False. At the end the count must be zero. For (() the count ends at 1, so the function returns False.

Exercise 10 (hard). Explain, in a short paragraph, why the palindrome check on the word racecar makes four calls, not seven, and what that means for the cost of checking a string of length n. Then state the stack depth.

Show the answer

The calls are (0, 6), (1, 5), (2, 4) and (3, 3). The last call sees left >= right and returns True, so it makes no comparison. There are four calls for seven letters, about half the length plus one. For a string of length n the calls go up to about n / 2, so the time is O(n). The stack depth is the same, about n / 2 frames, which is also O(n). The check stops early for a word that fails, so the best case is a single call.

What you now know

• A list or string is indexed from 0, and len(data) is one past the last index.
• Move an index toward the end, handle the current element, and let the recursive call handle the rest.
• A base case must match the problem: an empty range for a sum, a single element for a maximum.
• The palindrome check uses two pointers moving inward, and it stops when the pointers cross.
• Copying a list or string on every call turns an O(n) function into O(n squared), so pass an index instead.
• Plain Fibonacci repeats work and takes O(2^n) time. A dictionary or @cache stores each answer once and brings the time down to O(n).
• An out-of-range index raises IndexError, and the message is list index out of range or string index out of range. Python does not name the bad index, so read the traceback line.