Python Programming Basics to Advanced | Recursive Functions and Memoization | Lab 28

This Python programming playlist is designed to take beginners with zero programming experience to an expert level. The course covers installation, basic syntax, practical scenarios, and efficient logic building. The course material includes PDF handouts, review questions, and covers a wide range of topics, from data types to advanced functions like Lambda and Recursive functions, Generators, and JSON data parsing.

In this lesson we will study about two topics: Recursive Functions and Memoization. Recursive functions are the functions which call itself. We will compare the performance and complexity of Recursive and Non-Recursive functions and will see how we can use the concept of Memoization to improve the performance of any function.

Complete Playlist:

If you have the basic programming knowledge and interested to learn Object-Oriented Programming in Python, check out this playlist:

Lab Manual 28 can be downloaded from here:

Review Question:
1-Do a complete comparison of Recursive and Non-recursive function for the Factorial function. In comparison you have to discus following things:
- Complexity of non recursive and recursive function (without memoization).
- Improvement in complexity with memoization on Recursive function.
- Using lru_cache for memoization, what is minimum value of maxsize that can work.
- For a general number n, what should be minimum recursion limit which will not generate the RecursionError.
2- The Greatest Common Divisor (GCD) of two numbers can be found recursively as:
- Input arguments are two number a and b
- if second number is 0, return a.
- otherwise return GCD of a and a%b
Implement the GCD function with this logic.

#PythonProgramming #python #pythontutorial

[hassanniaz]

Spent a lot of time but it was surely worth it. Here's the code to the "TOWER OF HANOI" problem:
def PrintHanoiTower():
for j in range(disks):
for i in range(len(Tower)):
print(f"{Tower[i][j]}\t", end="")
print()
print("--\t--\t--")
print("1\t2\t3\t")
print()
print()

def HanoiTower(numDisks, source, intermed, destination):
if numDisks==0:
return
HanoiTower(numDisks-1, source, destination, intermed)
def move(start, end):
nonlocal numDisks


for i in range(disks-1, -1, -1):
if Tower[end][i]==0:
Tower[end][i]=numDisks
break
move(source, destination)
PrintHanoiTower()
HanoiTower(numDisks-1, intermed, source, destination)

disks=eval(input("How many disks do you want >> "))
Tower=[[], [], []]
for i in range(1, disks+1):
Tower[0].append(i)
Tower[1].append(0)
Tower[2].append(0)
PrintHanoiTower()
HanoiTower(disks, 0, 1, 2)


:)

[hamidiftikhar]

q#1:-
The complexity of the Recursive function without memoization will be more than Non-Recursive function it repeat the same function several times, that will create greater number of nodes.




With memoization:- Recursive functions will take less time, as it can store previous calculations and use these calculations instead of calculating it again.



There is no use of memoization in case of factorial function because there is no repeated calculations. But in case when there are more than one number then we will use memoization to avoid repitation in the calculations.



Default recursion value is 1000 but we can change it by using (sys) module.






q# 2:-
def gcd(x, y):

if y==0:

return x

else:

return gcd(y, x%y)


#Main program


l=eval(input("Enter first number= "))

m=eval(input("Enter second number= "))

print(gcd(l, m))

[abdul-hadi]

#Review_Question_1

-As Expected the recursive function is more complex as indicated by the time of execution. Non recursive on the other than takes much less time.
-Memoization reduces the execution time as, we are using previous outputs to skip calculations and save time. But in case of factorial since there are no useful previous outputs corresponding to inputs so it doesn't
affect the run time.
-Since memorization has no use here so the value of max size doesn't matter. It is the no of recent call results stored and then used to improve performance. In any other recursive function where memorization helps to increase performance the discussion is revelent as to what minimum value just it have to fully store all the results that will be used.
-Minimum Recursion limit is 2n

#Review_Question_2
def GCD(a, b):
    if b==0:
        return a
    else:
        return GCD(b, a%b)

[talhakamboh]

1) Complexity of Recursive function is higher than the non-recursive one.
2) By memorization, we can reduce the time of code execution. We can store the calculations and use them in repetitions if more than one number is available in a function. With memorization, we can lessen the complexity.
3) Using Iru_cache can be useful if we have to find factorial of more than one number But there's no need of it in case of one number.
4) default value of recursion is 1000 but we can change it by sys module.

#Review_Question2
def GCD(a, b):
if(b==0):
return a
return GCD(b, a%b)
N1=eval(input("Enter a number : "))
N2=eval(input("Enter a number : "))
print(GCD(N1, N2))

[muhammadshess]

1: The complexity of the recursive function without memoization is higher than the non-recursive function as we know that for recursive function without memoization O(n)=2^n while for non-recursive function O(n)=n.
Moreover, for example, time for execution of fact(100) with recursive function without memoization is while for non-recursive function is So, from this example a clear difference can be seen for complexity level of both methods.

2: There will be great improvement in the complexity of recursive function if we use memoization such that from O(n)=2^n to O(n)=n. In this case no of recursions reduces than the previous case as the nodal cal can be replaced by already calculated results.

3: Memoization will work only if there is repetition of numbers. In case of factorial of single number it has no work but will be useful if we have to find factorial of more than one numbers.

4: For a general number n, the minimum recursion limit which will not generate the RecursionError is 1000 which is set by default, we can also change it if we want by using sys module.

#REVIEW_QUESTION_2:
def gcd(a, b):
if b==0:
return a
else:
return gcd(a, a%b)

#MAIN PROGRAM#
a, b=eval(input('Enter the numbers(a, b): ')
print(f'GCD of {a} and {b} is {gcd(a, b)}')

[zainzakir]

Assalam-o-Alaikum Sir!
QUESTION NO:1
1) Complexity of Recursive function is higher than the non-recursive one.
2) By memorization, we can reduce the time of code execution. We can store the calculations and use them in repetitions if more than one number is available in a function. With memorization, we can lessen the complexity.
3) Using Iru_cache can be useful if we have to find factorial of more than one number But there's no need of it in case of one number.
4) default value of recursion is 1000 but we can change it by sys module.

Question no 2:
def GCD(a, b):

if(b==0):

return a

return GCD(b, a%b)

N1=eval(input("Enter a number : "))
N2=eval(input("Enter a number : "))
print(GCD(N1, N2))

[AliIrfan-soxf]

Recursive Function are more complex than non-recursive because of more no. of calculations.
- in memorization the calculations are stored and can be used in case of repetition, this reduces time and complexity.
- in case of a single no. factorial, no memorization is needed. but its needed when the calculation occurs repeatedly.
-Default recursion value is 1000 but we can change it by using sys module.


Q 2:
def GCD(a, b):    if(b==0):        return a    return GCD(b, a%b)n1, n2=eval(input("Please enter two numbers (seperated by comma): "))print(GCD(n1, n2))

[waleedraza]

Q#1
1. without memorization, the complexity of recursive function will definitely be more, using the technique, it can be reduced
2. with memorization, the number of nodes on each side of the series can be calculated, and others can use the value from the cachee storage.
In General, with memoization, recursive function took less time than non-recursive function.
3. The default value of the recursive function is 1000, but it can be changed by using the sys module
Q#2def GCD(a, b):
if b==0:
return a
else:
return GCD(b, a%b)
print(f'The GCD of 20 & 30 is: {GCD(20, 32)}')

[MuhammadAhmad-dshu]

Question No. 1:-

Recursive function will be more complex because its complexity will be O(n) and their will be more nodes when used without memoization. It is also evident from the execution time of both functions.

With memoization, there will be very improvement in the recursive function as the number of calculations will be decreased because the values once calculated will be used instead of calculating again.

Minimum value of maxsize in memoization is 1 as cache can store upto maxsize. It will be used when atleast 1 value will be stored because it is used for more than one values.

Recursion limit is due to the stack memory and default value 1000 is good but can also be changed if needed.

Question No. 2: -

def gcd(a, b):
if b==0:
return a
else:
return gcd(a, a%b)

num1=eval(input("Enter first number: "))
num2=eval(input("Enter second number: "))
gcd(num1, num2)

[hishamawan]

Task 1)
- If memoization is not used, then it takes a long time for the recursive function to give a bigger value of higher order . Non-recursive function has difficult logic but it takes less time.
- With Memoization the recursive function gives the answer in a shorter time period.
- 499 is the maximum size for which we can calculate the factorial.
- By default, 1000 inner calls to recursive function can be made.

Task 2)
from functools import lru_cache
@lru_cache()
def GCD(x, y):
if(y==0):
return x
else:
return GCD(x, x%y)

# Main Program #

print(GCD(10, 20))

[muhammadalihaider]

#Q1
i. Recursive function without memoization are more complex than Non-Recursive function the same function is called several times creating more nodes
ii. With memoization, recursive functionsbecome less complex i.e. from 2^n (without memoization) to just n (with memoization) ultimately reducing calculation time by using already calculated data from cache memory.
iii. For factorial on one number, memoization will be of no use as there is no repetition in the factorials. However, it will reduce complexity and calculation time in case of more than one numbers.
iv. Minimum recursion limit for general number n should be 2n+1 (because factorial function invloves double recursion)

​#Q​2
def GCD(a, b):
if b==0:
return a
else:
return GCD(b, a%b)
print(f'The GCD of 20 & 30 is: {GCD(20, 32)}')

[zainulhassan]

The complexity of recursive function will be more without memorization. However, by using the technique it can be reduced.
The number of nodes on each side of the series can be calculated with memorization and others can use the value from the cachee storage.
However, in general cases, the recursive function took less time than non-recursive function.
The default value of the recursive function is 1000 but it can be changed by using the sys module.

#Review Question
def GCD(a, b):
if b==0:
return a
else:
return (b, a%b)
d=int(input("Enter first number:"))
e=int(input("Enter second number:"))
print(GCD(d, e))

[fourcloversan]

Q1:

Complexity : Recursive function without memoization will be more complex than Non-Recursive function as it calls the same function several times thus creating larger number of nodes

Improvement: With memoization, the complexity of recursive functions reduces largely i.e. from 2^n(without memoization to just n(with memoization) & thus reducing the calculation time by using already calculated data from cache memory.

Min value: For factorial on one number, memoization will be of NO use as there is no repetition in the factorials. However, it will reduce complexity and calculation time in case of more than one numbers.

Recursion error: Minimum recursion limit for general number n should be 2n+1 (because factorial function invloves double recursion)



Q2:

def GCD(a, b):
if b==0:
return a
else:
return GCD(b, a%b)

a=eval(input('Enter 1st Number :'))
b=eval(input('Enter 2nd Number :'))
print(GCD(a, b))

[dawood]

1. without memorization, the complexity of recursive function will definitely be more, using the technique, it can be reduced
2. with memorization, the number of nodes on each side of the series can be calculated, and others can use the value from the cachee storage.
In General, with memoization, recursive function took less time than non-recursive function.
3. The default value of the recursive function is 1000, but it can be changed by using the sys module.

##Review_GCD
def GCD(a, b):
if b==0:
return a
else:
return (b, a%b)
d=int(input("Enter first number:"))
e=int(input("Enter second number:"))
print(GCD(d, e))

[MuhammadHassan-ldyt]

2019-MC-17



Question 01

-In Recursive function for the Factorial function, without Memoization there is
much complexity than non-recursive function because as more calculations are needed in case of recursive so it will take more time.

- With Memoization, when calculations that have already been calculated are used
again, function will used them instead of calculating again. So recursive functions with memoization will take lesser time.

- Using lru_cache for memoization, minimum value of maxsize is 128 bits.
- For a general number n, I think minimum recursion limit which will not generate the RecursionError is 2(n+1) (not sure about it).


Question 02

def GCD(a, b):
if (b==0):
return a
else:
return GCD(a, a%b)

print(f'The GCD of 10 and 60 is {GCD(10, 60)}')

[usman_tariq]

#Q1:-
1: Recursive functions are more complex than non-recursive functions without any memoization because of more nodes and their repeatedly calculations. This will also be evident from the time execution of both functions.
2: With memoization there will be great improvement in case of recursive functions because there is no repeated calculations at nodes and the already calculated results from cache memory (where data stored) will be used instead of same repeatedly calculations thus reduces the execution time of the program.
3: There is no use of memoization in case of factorial function because there is no repeated calculations however if we wish to calculate factorial of more than one numbers then ofcourse it will be useful.
4: The default value of recursion is 1000 but we can change it by using sys module.

#Q2:-
def gcd(a, b):
if(b==0):
return a
else:
return gcd(b, a%b)
a=eval(input('Enter first number: '))
b=eval(input('Enter second number: '))
print(gcd(a, b))

[haris]

Qs 1:
1- The complexity of Recursive function will be higher (O(n)=2^n) than Non Recursive function (O(n)=n), without any memoization, due to bigger number of nodes and their calculations. This will be evident from the great difference between the exection time of two functions.



2- There will be an immense improvement in the complexity of Recursive Function with memoization (from 2^n to just n). As now the extraneous nodal calculations can be replaced by already calculated results retrieved from the cache.



3- If there only one number for which the factorial is to be calculated then memoization is of no use. But it can prove fruitful, if factorials of more than one numbers are required.



4- Default recursion value is 1000 but we can change it by using sys module.






Qs 2:
def GCD(a, b):
if(b==0):
return a
return GCD(b, a%b)

n1, n2=eval(input("Enter two numbers (seperated by comma): "))
print(GCD(n1, n2))

[yusrakashif]

Q1)
Recursive function is more complex than non recursive(without memorization)as it repeat itself again and again and will take more time.
Recursive functions will take less time (with memorization) as it can store previous calculations and use them instead of calculating it again.
In factorial recursive function of single number, memorization is not useful while in case of many numbers
it can be.
For general number n the recursive error can be avoided by setting the recursive limit to 2(n+1).
Q2)
def GCD(a, b):
if b==0:
return a
else:
return GCD(b, a%b)
a=eval(input("Enter first number="))
b=eval(input("Enter second number="))
print(GCD(a, b))

[dawoodimtiaz]

1)## Recursive Funtions are more complex than non-recursive functions without the memoization because it repeats the same function and more number of notes and again repeatedly calculations. And we can also verify this by time execution of both functions.
##In recursive function with memoization there will be a great improvement in the calculation as it stores previous calculations and use that rather than calculating the same calculation again.
##In the case of factorial function there is no need to use memoization because there is no repeating calculations. However, if we want to calculate the factorial of more than one number then we will use memoization to avoid repetititon.
##Default Value of recursion is 1000 but we can change it by using sys module.


Q2) def GCD(a, b):
if b==0:
return a
else:
return GCD(b, a%b)

a=eval(input('Enter 1st Number :'))
b=eval(input('Enter 2nd Number :'))
print(GCD(a, b))

[abdulrehmankhalid]

_ Recursive function are more complex to perform because they have to call itself again and again so time taken will increase exponentially with the each time the function is being called. Like order of recursive function=2^n while for non-recursive function=n.
_Performance of recursive function can be improved by using memoization approach in which results are being stored in cached and further if they are called in other certain call so instead of doing all the stuff again results will be picked from cached and time will saved.
_ So Memoization will ensure that method will not execute more than once so it will be useful where more than once calls are interlinked
_ Default value is 1000 times, but it can be change from "sys" module to desire limit.

#Review_Question
def GCD(a, b):
if(b==0):
return a
return (GCD(b, a%b))
x1, x2=eval(input('Enter two integers separated by comma(y, z):'))

print(f'GCD is:{GCD(x1, x2)}')