🔒 I don't understand how a recursive function can call the last recursions after assignment.

[polar shadow]

In the recursive function searchRec2, the variable recS is used to track the index of a target value in a list. I believe I understand up to the part where recursion happens till the element is found but how does the value of recS change as the recursion unwinds, and why is it important to add 1 to recS when returning from each recursive call?

Specifically, how does the function correctly return the index of the target value in the original list, and why does recS not remain 0 even after the target is found?

def searchRec2(A, k):
    if A == []:
        return -1  # Base case: If list is empty, return -1
    if A[0] == k:
        return 0  # If element found, return 0
    recS = searchRec2(A[1:], k)  # Recursive call on the rest of the list
    if recS == -1:  # If the element wasn't found in the rest of the list
        return -1
    return recS + 1  # Add 1 to the returned index to account for the current element

[wooden mango]

@polar shadow

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[polar shadow]

def searchRec2(A, k):
    if A == []:
        return -1  # Base case: If list is empty, return -1
    if A[0] == k:
        return 0  # If element found, return 0
    recS = searchRec2(A[1:], k)  # Recursive call on the rest of the list
    if recS == -1:  # If the element wasn't found in the rest of the list
        return -1
    return recS + 1  # Add 1 to the returned index to account for the current element```

I understand it slices the list till A[0] is equal to the target value

but I don't understand how recS +1 wil give you the index?

Isn't recS = 0 ? or is recS equal to the subset of the original list or what?

[rich patrol]

recS is result of the closest nested call.
Each nested call is done on a copy of the list without the first element.
The +1 is done to compensate for that cutting when we get our cut off element back.

Let's give it a list(range(10)) and find 5. In this example value is the same as original index.
But each nested call will be done without first element of the previous - so first nested call will be done on 1-9, second on 2-9, and so on. Until we get 5-9.
Now, current list's [0] is equal to our searched value. We return 0 - our searched value is in 0th index.
In the call with list 4-9 the recS is therefore 0. But 5 is no longer at 0, when exiting we get our removed elements back. So we gotta return that +1.
Same when we get back to the recursion with 3-9 list. recS is now 1. But we got an element back, so we gotta +1 again. We return 2.
And so on.
2-9 returns 3, 1-9 returns 4, then our original returns 5.

[polar shadow]

So it keeps recursing even after the target value is reached??

I don't see why it would check 4-9 if it already returned 0

How does it get it's removed elements back? Is that just a property of recursion?

It recurses until it needs to stop and then proceeds to follow the rest of the code for each recursion?

[rich patrol]

It doesn't check again.
Each call to another function makes current function be put aside, with the current line saved.
When the inner function returns, we get back to the function that called it.
It's nested. Any return is just removing one level of nesting.

Lets say we have a list with a, b, c, d and we want to find c.

Outside code calls func with abcd list:
  - check ifs - we didn't return
  - call the recursion with bcd list:
    * we're inside the new call
    * check ifs - we don't return
    * call function again with cd list:
      ~ another inner call...
      ~ check ifs - we return 0 
    * we get back to where we were called, saving the result inside recS
    * we check the later if - we don't return there
    * now we return recS+1, meaning we return 1
  - we get back to were the function was called, save the result of the call in recS, meaning current recS=1
  - we check the later if, but don't return
  - we reach return recS+1, so we return 2
Outside code that called the function originally gets the 2 as result

Each recursive call is such nesting (that's why now I chose a shorter list now, I didn't want to write out such long nesting)

[polar shadow]

Thank you very much, I believe I understand around 85% of what you are trying to tell me. I guess with time and practice it will get easier 👍

[rich patrol]

You can add print(f"searchRec2({A}, {k}) before calling the inner function")
and print(f"searchRec2({A}, {k}) after the inner function returned {recS}") to your function and just see what happens where - first you get many befores when you go 'in', then the afters in the opposite order when the recursion slowly exits 'out'

[wooden mango]

Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.