CODEWITHSUNDEEP
pythonfunctionrecursion
calvin2011
calvin2011

Reputation: 387

Could anyone show me how the recursive part of this function works?

I've been given an example of a recursive function and I just need some help understanding it.

I know that recursive functions a) must have a base case, b) must change the arguments and move towards the base case and c) must call itself

The code is below:

def func(x,y):
   if y == 0:
       return 0
   else:
       return x + func(x,y-1)

I'm just struggling to understand the func(x,y-1). I know the function returns the product of x and y but I'm not sure how the recursive part of the function works.

Upvotes: 1

Views: 351

Answers (7)

user3814579
user3814579

Reputation: 101

Structure and Interpretation of Computer Programs (SICP) describes an iterative process as one which "carries with it" all the information needed to solve the problem, while a recursive process has to "remember where it came from" in order to solve the problem.

One way to see the distinction is to trace how the length of the problem grows and then shrinks as it is being solved.

def func(x,y):
   if y == 0:
       return 0
   else:
       return x + func(x,y-1)

func(5,4)
func(5,4) --> 5 + func(5,3)
func(5,4) --> 5 + func(5,3) --> 5 + func(f,2)
func(5,4) --> 5 + func(5,3) --> 5 + func(f,2) -- > 5 + func(5,1)
func(5,4) --> 5 + func(5,3) --> 5 + func(f,2) -- > 5 + func(5,1) --> 5 + func(5,0)
func(5,4) --> 5 + func(5,3) --> 5 + func(f,2) -- > 5 + func(5,1) --> 5 + func(5,0) --> 0
func(5,4) --> 5 + func(5,3) --> 5 + func(f,2) -- > 5 + func(5,1) --> 5 + 0
func(5,4) --> 5 + func(5,3) --> 5 + func(f,2) -- > 5 + 5
func(5,4) --> 5 + func(5,3) --> 5 + 5 + 5
func(5,4) --> 5 + 5 + 5 + 5
5 + 5 + 5 + 5
20

Upvotes: 0

Loftur Bjarnason
Loftur Bjarnason

Reputation: 51

As you said, the function keeps calling itself. If it had been like this:

def func(x,y):
    return func(x,y)

it would endlessly call itself and wouldn't give you a result.

However if you make y smaller with every call, you can stop the "madness" at some point, e.g. when y reaches zero. Then if y is 1 smaller every time, func(2, 2) would call func(2, 1) which would call func(2, 0) which would finally return a value because by then y=0. func(2, 1) uses that value and adds "x" to it, and so on. Finally func(2, 2) would add x to that return value. The return is then x times y function calls or 2*2.

Upvotes: 0

anmonteiro
anmonteiro

Reputation: 210

I should also say that the following optimization should be done: if y == 0 or x == 0:, or a call to func(0, 1000) would needlessly put values in the stack

Upvotes: 0

Kasravnd
Kasravnd

Reputation: 107347

your function decrease the value of y every times till it got 0 then in every call you remain a x so depend on the value of y you have the sum of x actually the function is y*x

>>> def func(x,y):
...    if y == 0:
...        return 0
...    else:
...        return x + func(x,y-1)
... 
>>> func(3,4)
12
>>> func(3,0)
0

for example for func(3,4) your function return this :

 3 + func(3,3)= 3+ func(3,2) = 3 + func(3,1) = 3 + func(3,0)= 3+0

if we replace the funcs , we would have : 3+(3+(3+(3+0))) that is equal 12 .

Upvotes: 1

chepner
chepner

Reputation: 532268

We'll assume that func is a function which returns the product of its two arguments (assuming y is a non-negative integer). It's clearly true when y is 0, because

if y == 0:
    return 0

and x * 0 is 0 for any value of x. Otherwise, it returns x + func(x, y-1), and since we are assuming that func(x, y-1) returns the product of x and y-1, we can confirm that

x + x*(y-1) = x + x*y - x
            = x*y

so func(x, y) indeed returns x * y for any x and any non-negative integer y.

My college professor use to tell us to "trust your recursion". When making recursive calls, simply assume that it the recursive call will return "the right thing" when writing the recursive case; as long as you are properly making the recursive call "simpler" than the original call, it will "just work".

Upvotes: 0

Prakhar Awasthi
Prakhar Awasthi

Reputation: 23

func(x,y-1) simply calls func again with new values x & y-1 For example, take x=5, y=6 first call will be: func(5,6) after that, It'll call func(5,5) -> func(5,4) -> func(5,3) -> func(5,2) -> func(5,1) -> func(5,0)

at last func(5,0) will return 0 to its caller. & It'll go all the way up to the first call...

In short, every time that function recurs, It calls Itself with one less value of y (i.e. second variable) & eventually It'll terminate when y=0.

Upvotes: 0

SMA
SMA

Reputation: 37093

This function is adding x element y times. So here's how it works:

When you call your func with 3, 2, you do the following:

  • you check if y is 0, if its 0 return 0. This is needed condition to return from recursion.
  • If its not zero, you do add 3 + fun(3, 1) This part goes to stack and it calls function again.
  • Again it checks y value and does 3 + func(3, 0). This part again goes to stack and calls function again
  • Now its 0, so it returns and pop's top elemnt from stack i.e. 3 + fun(3, 0) and now since fun(3, 0) returned 0 it will return 3
  • Again pop top element which we left i.e. 3 + fun(3, 1). fun(3,1) in previous step returned 3, so it will replace fun(3, 1) with 3 and return 3 + 3 = 6. -Now since you dont have any element on stack (i.e. no more function evaluation left), it returns 6 and returns back to the caller.

Upvotes: 0

Related Questions