The code is quite easy but its returning 'None', i do not know why. Can someone please correct my code.
def rev(x):
global y
if len(x)==0:
return y
else:
y=y+[x[-1]]
x.pop(-1) #Remove last item from list
rev(x)
z=[1,2,3]
y=[]
print(rev(z))
Thank you but I'm supposed to use recursion...
Recursion is a functional heritage and so using it with functional style yields the best results. This means avoiding things like mutation, variable reassignments, and other side effects.
t is empty, return the empty resultt has at least one element. prepend the result of the sub-problem rev(t[1:0) to a singleton list of the first element, [t[0]]def rev(t):
if not t:
return [] # 1. empty t
else:
rev(t[1:]) + [t[0]] # 2. at least one element
A function without side effects will always return the same result for the same input. This allows us to substitute and function call for its output and easily visualize its computational process -
rev([1,2,3,4,5])
== rev([2,3,4,5]) + [1]
== rev([3,4,5]) + [2] + [1]
== rev([4,5]) + [3] + [2] + [1]
== rev([5]) + [4] + [3] + [2] + [1]
== rev([]) [5] + [4] + [3] + [2] + [1]
== [] + [5] + [4] + [3] + [2] + [1]
== [5] + [4] + [3] + [2] + [1]
== [5,4] + [3] + [2] + [1]
== [5,4,3] + [2] + [1]
== [5,4,3,2] + [1]
== [5,4,3,2,1]
Notice the pyramid shape of the pending computations. As the input grows, the amount of singleton lists waiting to be combined grows. If t were significantly large, this would result in a stack overflow.
Let's see how one small adjustment can make a big impact on the process -
def rev(t, r = []):
if not t:
return r # 1. empty t, return r
else:
rev(t[1:], [t[0]] + r) # 2. at least one element, prepend to r
Instead of leaving pending computations for us to come back to, we introduce a second argument with a default value. Notice how the visualized process below stays linear and flat instead of growing like a pyramid -
rev([1,2,3,4,5])
== rev([2,3,4,5], [1])
== rev([3,4,5], [2,1])
== rev([4,5], [3,2,1])
== rev([5], [4,3,2,1])
== rev([], [5,4,3,2,1])
== [5,4,3,2,1]
When the recursive call is the last call of the function, it is said to be tail recursive. Being that recursion is the natural looping mechanism in functional languages, the compiler will detect these tail calls and effectively prevent the stack from growing, referred to as tail-call elimination.
myinput = "abcdefghijklmnopqrstuvwxyz"
print("".join(rev(myinput)))
print("".join(rev(myinput * 100)))
zyxwvutsrqponmlkjihgfedcba
RecursionError: maximum recursion depth exceeded
So why did Python fail to compute rev(myinput * 100)? While Python supports many functional features such as modules and first-class functions, it does not offer tail-call elimination and so our rev function above still overflows the stack. Combined with its relatively small stack size, this fact makes Python a terrific language to actually learn about recursion. In understanding its limitations, you will know what it means to write efficient algorithms and even come to understand how stack-safe infinite recursion is possible in other languages.
For example, here's one technique that enables infinite recursion by using Python's inspect module which allows us to compare stack frame data. The recursive function is converted to a while loop and when a tail-call is no longer detected, the final result is returned. Reza Bagheri offers detailed explanation of this technique in this article -
# tail_rec.py
import inspect
def tail_rec(func):
is_rec = False
t = []
def loop(*args):
nonlocal is_rec
nonlocal t
f = inspect.currentframe()
if f.f_back:
if f.f_back.f_back:
if f.f_code == f.f_back.f_back.f_code:
is_rec = True
t = args
return
while True:
try:
result = func(*args)
except TypeError:
raise Exception("function is not tail-recursive")
if is_rec:
is_rec = False
args = t
else:
return result
return loop
To enable the optimization, we simply add the tail_rec decorator to our function -
from tail_rec import tail_rec # <- import
@tail_rec # <- enable tail call elimination
def rev(t, r = []):
if not t:
return r
else:
return rev(t[1:], [t[0]] + r)
And suddenly Python recursion limits have vanished into nothingness -
myinput = "abcdefghijklmnopqrstuvwxyz"
print("".join(rev(myinput * 100)))
zyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcba
Here's an example of how you could reverse the contents of a list in situ without slicing or recursion (not that you'd ever want to do it this way):
def rev(x):
i = 0
j = len(x)
while (j := j - 1) > i:
x[i], x[j] = x[j], x[i]
i += 1
return x
print(rev([1,2,3,4,5]))
