CODEWITHSUNDEEP
pythonpython-3.x
KUJI BOI
KUJI BOI

Reputation: 33

Recursion Using Variables

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.)

Upvotes: 1

Views: 1392

Answers (4)

Tanner Clark
Tanner Clark

Reputation: 691

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: Recursive Case Description

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!

Upvotes: 3

stud3nt
stud3nt

Reputation: 2153

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.

PythonTutor

Upvotes: 2

navneethc
navneethc

Reputation: 1466

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.

Upvotes: 0

Mario Camilleri
Mario Camilleri

Reputation: 1567

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).

Upvotes: 0

Related Questions