Recursion in python

Question

I have a conceptual doubt about using recursion in python. Below is the python code for reversing a stack using only recursion which I have copied from this page at geeksforgeeks.

# Below is a recursive function that inserts an element
# at the bottom of a stack.
def insertAtBottom(stack, item):
    if isEmpty(stack):
        push(stack, item)
    else:
        temp = pop(stack)
        insertAtBottom(stack, item)
        push(stack, temp)
# Below is the function that reverses the given stack
# using insertAtBottom()

def reverse(stack):
    if not isEmpty(stack):
        temp = pop(stack)
        reverse(stack)
        insertAtBottom(stack, temp)

It seems like the function reverse is using stack as a global variable because the called function isn't returning any new value to the caller function. Isn't this a wrong way of implementing recursion? Shouldn't we avoid using global variables in stack?

Also, how would we edit this function such that each instance of the called function uses it's own copy of stack?

Please try to break your sentence down "What I wish ... function". This is a headache.. — Ma0
– Ma0, Commented Mar 7, 2017 at 10:24

GPhilo · Accepted Answer · 2017-03-07 11:43:58Z

1

Edit: reworking the phrasing to be more consistent with the terms used.

stack is not a global variable, it's a parameter of the function. You can imagine it as a reference to the stack object instance that was created somewhere else before calling the function. Operating on the parameter actually modifies the object referenced by it.

edited Mar 7, 2017 at 11:43

answered Mar 7, 2017 at 10:35

GPhilo

19.3k9 gold badges70 silver badges91 bronze badges

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

3 Comments

Open AI - Opting Out Over a year ago

You have a lot of similar terms, variable, parameter, reference, but you're using them quite inconsistently, even incorrectly.

GPhilo Over a year ago

Please elaborate on your comment. I updated my answer to make it clearer and more consistent with the terms, but I can't find any point in which I use the terms incorrectly.

Open AI - Opting Out Over a year ago

One problem for me was saying stack wasn't a variable, but was a parameter. Now you're making the distinction to do with scope, much better. Also you said operating on the parameter modifies the original variable, which is confusing. In some ways Python doesn't have variables. Names reference objects. You can change a name to reference a different object, or you can modify the object. So I like that you now say it modifies the object referenced by the parameter.

Open AI - Opting Out · Accepted Answer · 2017-03-07 10:35:39Z

0

push and pop will be modifying the object which stack is a name for. Everywhere stack is mentioned it is a name for the same object, because it is passed to reverse and insertAtBottom as a parameter named stack. No objects are copied, and neither are they global. You could name your parameters something different but it would still refer to the same object.

Whatever you pass into the reverse function will be used. It's not global, you have control over which object is used.

my_stack = []
reverse(my_stack)  # uses object *my_stack*

answered Mar 7, 2017 at 10:35

Open AI - Opting Out

24.3k7 gold badges65 silver badges102 bronze badges

Comments

Prashant Vlogs · Accepted Answer · 2019-05-13 07:13:15Z

0

Function calling itself is known as recursive function and this process is known as Recursion .For More detail this can help

answered May 13, 2019 at 7:13

Prashant Vlogs

111 bronze badge

Collectives™ on Stack Overflow

Recursion in python

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related