Can't understand how to store values for each step

Question

I am a beginner, trying to learn recursion and solve some problems (trying the subsequences problem). But before I could even attempt to get the recursion logic right, I am getting stumped while trying to store the values returned. Here is what I tried and the outputs I received. Experimented putting some print commands just to understand. I thought the following will give me answer = [[b,c],[c]] instead, it appears the stored value is "None". Hope someone can explain what I am doing wrong and how to correct this, so that I can then proceed with the subsequences problem. Thank you.

Arun

def subseq(arr, answer=[""]):
    if len(arr) == 0:
        return("")
    print("arr", arr)
    answer += subseq(arr[1:],answer)
    print("answer", answer)
arr = ['a','b','c']
subseq(arr)

#--------------------------------------------------------------------

I was hoing to get ['b','c'] and ['c'] as the answer but can't get that. Output is as follows: arr ['a', 'b', 'c'] arr ['b', 'c'] arr ['c'] answer [''] #This followed by the following error: answer += subseq(arr[1:],answer) #TypeError: 'NoneType' object is not iterable

Answer 1

Your code has other bugs as well.

Think of the recursion as:

1. What do you want to do in each recursion step
2. How does your input becomes smaller than before after doing the operation in step 1.
3. Doing recursion on a smaller part of input obtained in step 2.
4. Think about the base case where recursion needs to stop and put it at the top.

Thus, you need to modify your code in the following way. Please follow my comments.

def subseq(arr, answer):
    # Step 4: Base case
    if len(arr) == 0:
        return

    print("arr ", arr)

    # Step 1: Think about what you want to solve in each step
    subsequence = arr[1:]
    
    # collect your operation output in answer
    if len(subsequence) > 0:
        answer.append(subsequence)
    
    # Step 2: New input
    new_arr = arr[1:]  # should become smaller at each step


    # Step 3: Make more recursion
    subseq(new_arr, answer)

arr = ['a','b','c']
answer = []  # Allocate memory for storing answer before hand
subseq(arr, answer)
print("answer", answer)