How to write a recursive function in python

Question

I have been stuck on the solution to this question for quite a while i have written a piece of code that works as requested but i seems to get an error at the end of the compilation

You need to design an iterative and a recursive function called replicate_iter and replicate_recur respectively which will receive two arguments: times which is the number of times to repeat and data which is the number or string to be repeated.

The function should return an array containing repetitions of the data argument. For instance, replicate_recur(3, 5) or replicate_iter(3,5) should return [5,5,5]. If the times argument is negative or zero, return an empty array. If the argument is invalid, raise a ValueError.

my code is as below:

def replicate_iter(times,data):

    emptyArray = []
    if not isinstance(data, int) and not isinstance(data, str):
        raise ValueError
    if times <= 0:
        print emptyArray
    if not isinstance(times,int):
        raise ValueError
    else:
        while times > 0:
            emptyArray.append(data)
            times -= 1
        return emptyArray

array = []

def replicate_recur(times,data):

    if not isinstance(data,int) and not isinstance(data,str):
        raise ValueError
    if not isinstance(times,int):
        raise ValueError
    if times <= 0 and len(array) != 0:
        return array
    elif times <= 0 and len(array) <=0:
        return []
    else:
        array.append(data)
        replicate_recur(times - 1,data)

Kindly assist with suggestions please

error message : enter image description here

No sweat. Simply edit your question to contain the error message as text instead of as an image, so that it can be found by the search. — das-g
– das-g, Commented Nov 27, 2016 at 13:11

גלעד ברקן · Accepted Answer · 2016-11-27 14:33:42Z

1

First, think about this:

def f(times,data):
  return [] if times == 0 else f(times - 1,data) + [data]

print(f(3,5)) # [5,5,5]

Now, with regard to your recursive solution, (1) in order to access array, replicate_recur would need a declaration at its outset, "global array," since the variable, array, is declared outside of the function's scope; and (2) modify the recursive call, "replicate_recur(times - 1,data)," to "return replicate_recur(times - 1,data)," in order for the function to actually return a value when times is greater than zero. (That said, as I understand, it's generally considered undesirable form to have global accumulators for recursive functions.)

edited Nov 27, 2016 at 14:33

answered Nov 27, 2016 at 13:54

גלעד ברקן

24k3 gold badges29 silver badges64 bronze badges

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

4 Comments

MrTerfa Over a year ago

Thank you for the explanation. This worked for me. Could you kindly explain how the line works: return replicate_recur(times - 1,data) +[data] def replicate_recur(times,data): if not isinstance(data, int) and not isinstance(data, str): raise ValueError if not isinstance(times, int): raise ValueError if times <= 0: return [] else: return replicate_recur(times - 1,data) +[data]

גלעד ברקן Over a year ago

@MrTerfa with regards to the one-liner, think what f(times - 1,data) would return if times were 1. Now think what would that return value + [data] become? Then think, what if we had three calls like that in succession?

גלעד ברקן Over a year ago

@MrTerfa With regards to modifying your original recursion, when you first call the function with times greater than 0, the function is not expected to return anything. It does make another call to the same function which modifies the external array but simply returns nothing. When finally we get to the return array line, that return is not issued to the original call since there was no request for it. Prefixing the recursive call with return means we're expecting to return the value from the recursive call, which, when we get to return array, propagates through the previous calls.

MrTerfa Over a year ago

I understand it now. Thank you.

Alberto Pimenta · Accepted Answer · 2016-11-27 13:17:32Z

0

Maybe this is what you want based on the example you gave:

array = []
def replicate_recur(times, val):
    if(isinstance(times, int) and times > 0):
        array.append(val)
        return replicate_recur(times-1, val)
    return array
print(replicate_recur(3, 5)) # [5,5,5]



array = []
def replicate_iter(times, val):
    if(isinstance(times, int) and times > 0):
        for i in range(times):
            array.append(val)
        return array
    raise ValueError
print(replicate_iter(3, 5)) #[5,5,5]

edited Nov 27, 2016 at 13:17

answered Nov 27, 2016 at 13:11

Alberto Pimenta

464 bronze badges

Comments

Daniel · Accepted Answer · 2016-11-27 13:19:04Z

0

You must not use a global variable. A second call to your function leads to wrong results. Use a internal function or optional parameter instead.

def replicate_recur(times,data, array=None):
    if array is None:
        array = []
    if times <= 0:
        return array
    array.append(data)
    return replicate_recur(times - 1, data, array)

answered Nov 27, 2016 at 13:19

Daniel

42.9k4 gold badges57 silver badges82 bronze badges

Comments

Simon · Accepted Answer · 2016-11-27 13:50:26Z

0

Maybe you should split up the logic, always becomes more readable, so it becomes easier to implement. You should avoid global variables, especially global lists, they will cause you much pain.

def rep_rec(times, data, pack=[]):
    pack += [data]
    return pack if times < 2 else rep_rec(times-1, data, pack)


def replicate_recur(times, data):
    if not times or not data:
        return []
    if isinstance(times, int) and (isinstance(data, int) or isinstance(data, str)):
        return rep_rec(times, data) if times > 0 else []
    raise ValueError

answered Nov 27, 2016 at 13:50

Simon

4244 silver badges12 bronze badges

Comments

God Bennett · Accepted Answer · 2017-04-18 23:43:55Z



"""
A.  In recursions, in general, some input is minimized until some minimum condition.
    "eg: in f(x-2), x is the input" 



B.  In the following recursion, multiples of x "eg: x TIMES f(x-2)" are
    computed as x gets smaller and smaller by 2 "eg: f(x MINUS 2)", 
    until x finally reaches 1 "eg: if x==ONE return 1", the minimum CONDITION value.



C.  The recursion multiplies by many values generated by calls of function "f",
    until mininum is reached.
    "eg: x TIMES value-AT-f-CALL_a(x-2) TIMES value-AT-f-CALL_b(x-2)....



D.  When mininum CONDITION is reached, or in other words, when x reaches 1, the recursion 
    multiplies by 1, instead of another value generated by function "f" call.
    "eg: x TIMES value-AT-f-CALL_a(x-2) TIMES value-AT-f-CALL_b(x-2) TIMES 1"

    NOTE: This is why the recursion ends, as it no longer multiplies by value at f-call.



E.  In "TIMES 1" in D above, because 1 is the minimum RETURN value
    "eg: if x==1: return ONE", this means the minimum CONDITION is reached.

    NOTE: if we had x PLUS f(x-2), then the mininum value would be 
    ADDED TO (instead of multiplied by) the SUM (instead of the product).
"""

def f(x):
    """This is a recursive function f to generate product of x, as x decreases by 2"""
    if x == 1:
        return 1
    else:
        return (x * f(x-2))

Collectives™ on Stack Overflow

How to write a recursive function in python

5 Answers 5

4 Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

4 Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related