Recursion Using Variables

Question

I'm currently learning recursion and I've come across a website that provides solutions to certain problems. One of these problems is finding a value in an array and returning the index using recursion. The solution provided is below:

def searchRec2(A, k):    
   if A == []:        
      return -1    
   if A[0] == k:        
      return 0    
   recS = searchRec2(A[1:],k)    
   if recS == -1:     
      return -1    
   return recS + 1

What I don't understand from this code is when the code uses the variable recS to run each recursive call of the search, once it finds the corresponding value in the array would it not return 0, and that 0 would be stored in recS.

So when it does the last return statement of recS + 1, is it not just doing 0 + 1 which is 1? I don't understand how it gets a value other than 1. (The code works it gives the index of the element we are looking for in the array.)

run through the example on a piece of paper with a small array say A = [2,3,4,5] and k=2. Write down and keep track of the variables & you will see how they change at each recursion. — DrBwts
– DrBwts, Commented Dec 31, 2019 at 15:43
As a side note I would suggest replacing if A == [] with if not A which is more Python and also faster (than a more complex list comparison). — Cristian Ciupitu
– Cristian Ciupitu, Commented Dec 31, 2019 at 15:47
See also how variables are stored and treated in recursion function in python? — Cristian Ciupitu
– Cristian Ciupitu, Commented Dec 31, 2019 at 16:00

Tanner Clark · Accepted Answer · 2020-01-01 14:31:47Z

3

With these types of problems, it is best to use a small example to see what is happening. Take A = [1,2,3] and k = 3. (Answer will be 2) Since the function calls itself, this occurs:

When the value is found, 0 is returned from the last function call. Then, 1 is returned from the second to the last call. Similarly, 2 is returned from the third to last call. (Which was our initial call)

Thus, the final return is 2.

Another way to look at it is that the function is recursively called until it finds your k value. Once it finds your value, it stops calling new functions and starts returning values. These returns follow up the chain of function calls, increasing by 1 after each return.

You can now start to see how this can apply to larger lists!

edited Jan 1, 2020 at 14:31

answered Dec 31, 2019 at 15:48

Tanner Clark

6811 gold badge8 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

KUJI BOI Over a year ago

Thank you very much, makes a lot of sense now!

stud3nt · Accepted Answer · 2019-12-31 15:43:05Z

2

The code works on the basic principle of recursion. Every time it does not find the element at the position it will keep incrementing the value of variable recS by 1. If the element is not found and it reaches at the last element then it simply returns -1.

I'd highly suggest you to use PythonTutor to visualize the code which you are running.

answered Dec 31, 2019 at 15:43

stud3nt

2,1811 gold badge14 silver badges25 bronze badges

2 Comments

KUJI BOI Over a year ago

Thanks for the reply makes sense now and I will definitely use PythonTutor from now on

stud3nt Over a year ago

You're welcome. Please upvote or mark it as answer if it has helped.

Mario Camilleri · Accepted Answer · 2019-12-31 15:38:13Z

0

The function searchRec checks the item at the head of the list and then calls itself recursively on the rest (the tail) of the list. So if the item is in location 5 of the list, searchRec would have called itself recursively 5 times (i.e. the recursion depth is 5). This last call returns 0, to which the previous call adds 1, and the call previous to THAT adds another 1, ... and so on back to the first call which returns 5 (we say the recursion UNWINDS).

answered Dec 31, 2019 at 15:38

Mario Camilleri

1,59718 silver badges29 bronze badges

1 Comment

KUJI BOI Over a year ago

Ty for the reply makes sense now

navneethc · Accepted Answer · 2019-12-31 15:41:38Z

0

It would return 0 at the specific recursive call at which k is the first element. It could happen at the first level of recursion or somewhere further up the stack, depending on where it is on the original list. Once it's found, the previous call would send back a 0+1; the next one up would return 0+1+1, and so on.

I would suggest taking a simple input (e.g. a short sequence of distinct numbers) and applying the algorithm using pen and paper.

edited Dec 31, 2019 at 15:41

answered Dec 31, 2019 at 15:36

navneethc

1,4761 gold badge11 silver badges22 bronze badges

1 Comment

KUJI BOI Over a year ago

Thanks for the reply, I understand it a lot better now

Collectives™ on Stack Overflow

Recursion Using Variables

4 Answers 4

1 Comment

2 Comments

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

2 Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related