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?

• Ma0: Please try to break your sentence down "What I wish ... function". This is a headache..
• Open AI - Opting Out: stack is not global, it's being passed into the function.

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

• Open AI - Opting Out: You have a lot of similar terms, variable, parameter, reference, but you're using them quite inconsistently, even incorrectly.
• GPhilo: 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: 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.

Answer 2

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*

Answer 3

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