Lesson Recursion - Artificial Intelligence - ثالث ثانوي

2. Artificial Intelligence Algorithms In this unit, you will learn about some fundamental algorithms used in Al. You will also create a simple rule-based medical diagnosis system with multiple programming approaches and compare their results. Finally, you will learn about search algorithms and how to solve maze puzzles when taking multiple parameters into account. Ministry of Education 70 2024-1446 Learning Objectives In this unit, you will learn to: > Create recursive code. > Differentiate between Breadth-first search and Depth-first search algorithms. > Describe search algorithms and their application. > Compare search algorithms. > Describe a rule-based system. > Train artificial intelligence models so they can learn to solve complex problems. > Evaluate the results of your code and the efficiency of your program. > Develop programs to solve simulations of real-life problems. > Compare search algorithms. Tools > Jupyter Notebook

Lesson 1 Recursion Dividing the Problem In this lesson, you will use recursive functions to make your program more intuitive and efficient. If your parents brought you a gift and you were eager to know what it was, but when you opened the box you found a new box inside that box, and thereafter there were boxes inside boxes, you would not know in which of those boxes the gift was. Recursion Recursion is one of the ways to solve problems in computer science, by dividing a problem into a group of small problems similar to the original problem so that you can use the same algorithm to solve those problems. Recursion is used by the operating system and by other applications, and most programming languages support it as well. Recursion occurs when the same instructions are repeated but with different data and less complexity. وزارة الته Ministry of Education 1446 Open the box Is there a box inside? No Yes You have found the gift and finished the recursion Figure 2.1: An example of recursion. Link to digital lesson www.ien.edu.sa 71

Let's look at an example of a function that calls another function. def mySumGrade (grades List): sumGrade=0 1=len(grades List) for i in range(1): sumGrade=sumGrade+gradesList[i] return sumGrade def avgFunc (grades List): s=mySumGrade(grades List) 1=len (grades List) avg=s/l return avg # program section grades [89,88,98,95] averageGrade-avg Func(grades) "I The mySumGrade function is called. print ("The average grade is: ', averageGrade) The average grade is: 92.5 The len() function takes a list as an input argument, which counts and returns the number of items in the list. Recursive Function In some cases, it is possible for a function to call itself, and and this property is called a recursive call. The general syntax of the recursive function: # recursive function def recurse Function(): if (condition): # base case else: statement #recursive call recurse Function () Main program recurseFunction() #main program # normal function call recurse Function() وزارة التعليم Ministry of Education 72 2024-1446 condition True False A recursive call is the process by which a function calls itself. statement Figure 2.2: Representation of a recursive call

The recursive function consists of two states: Base case This is the state in which the function stops calling itself, and access to the base case is verified through a conditional statement. Without the base case, the self-recall process will be infinite. Recursive case This is the state in which the function calls itself when the stop condition is not met, and the function remains in this self-recalling state until it reaches the base state. Common Examples of Recursion One of the most common examples of using recursion is the process of calculating the factorial of a specific number. The factorial of a number is defined as the product of all natural numbers smaller than or equal to that number. The factorial is expressed by the number followed by the symbol "!". For example, the factorial of 5 is 5! and 5!=5*4*3*2*1. Table 2.1: Factorials from 0! to 5! Notice that the process of calculating the factorial is based on the rule below 0! 0! = 1 1! 1!= 1*11 or 1! = 0!*1 2! 2! = 2*1=2 or 2! = 1!*2 1 if n=0, Base case n! = (n-1)!n if n>0 3! - 3! 3*2*16 or 3! = 2!*3 Recursive case 4! 4! = 4*3*2*1 = 24 or 4! = 3!*4 5! 5!=5*4*3*2*1= 120 or 5! = 4!*5 Figure 2.3: The rule of calculating the factorial Let's create a factorial loop that calculates the factorial of the number using the for iteration. # calculate the factorial of an integer using iteration def factorialLoop(n): result = 1 for i in range(2,n+1): result = result i return result #main program num = int(input("Type a number: ")) f=factorialLoop(num) "I print("The factorial of num, is:", f) ' وزارة التعليم Ministry of Education 2024-1446 Type a number: 3 The factorial of 3 is:6 73

Now let's calculate the factorial of a number using a factorial function. # calculate the factorial of an integer using a # recursive function def factorial(x): if x == 0: else: Base case return 1 return (xfactorial(x-1))• # main program num = int(input("Type a number: ")) f=factorial(num) "I factorial(3) 3 * factorial(2) Recursive case 2 * factorial(1) print("The factorial of ", num, is: ", f) Type a number: 3 The factorial of 3 is: 6 1 * 3! = 3*2*1=6 factorial(0) 1 Figure 2.4: Recursion tree Table 2.2: Advantages and disadvantages of recursion Advantages Recursive functions reduce the code segment to a smaller number of instructions. • A task can be broken down into a set of sub-problems using recursion. • Sometimes it's easy to use recursion to replace nested duplicates. Recursion and Iteration Disadvantages • Sometimes it is difficult to follow the logic of recursive functions. • Recursion requires more memory and time. • It is not easy to define cases in which recursive functions can be used. Recursion and iteration are both involved in executing a set of instructions a number of times, and the main difference between recursion and iteration is the way in which a recursive function is terminated. A recursive function calls itself and ends its execution when the base state is reached. An iteration is executed repeatedly until a specific condition is met or a specific number of iterations has elapsed. Some of the differences are reviewed between recursion and iteration are given the following table. Table 2.3: Recursion and Iteration Iteration Fast execution. Needs less memory. The size of the code is larger. Ends. by completing the specified number of iterations · or satisfying a condition. Recursion Slower execution compared to iteration. Needs more memory. The size of the code is smaller. Ends upon reaching the base state. وزارة التعليم Ministry of Education 74' 2024-1446

When do you use recursion? • In many cases it is considered a more intuitive way of dealing with a problem. • Some data structures are easy to explore using recursion. • Some sort algorithms, such as quick sort, use recursion. In the following example, you will extract the largest number in a list of numbers using a recursive function. Also shown is another function using iteration for the purpose of comparison. def findMaxRecursion (A,n): if n==1: m = else: m = return m A[n-1] max(A[n-1],findMaxRecursion(A,n-1)) def findMaxIteration (A,n): m = A[0] for i in range(1,n): m = max(m,A[i]) return m # main program myList [3,73,-5,42] ι = 1 = len(myList) myMaxRecursion = findMax Recursion (myList, l) The max() function returns the element with the highest value (the largest valued element in myList). print("Max with recursion is: ", myMaxRecursion) myMaxIteration = findMaxIteration(myList,l) print("Max with iteration is: ", myMaxIteration) Max with recursion is: 73 Max with iteration is: 73 وزارة التعليم Ministry of Education 2024-1446 max(A[3], findMaxRecursion (A, 3)) 42 <max(A[2], findMaxRecursion(A, 2)) -5 < max(A[1], findMaxRecursion(A, 1)) 73 3 Figure 2.5: The recursion tree of the function to extract the largest number in a list of numbers 75 75

In the next program, you will create a recursive function to calculate the power of a number. The program will accept a number (base) and an index (power) from the user, and you will use the powerFunRecursive() recursive function which will use these two arguments to calculate the power of the base number to the exponent. The same can also be achieved with iteration, and an example is included. def powerFun Recursive (baseNum, expNum): if(expNum==1): return(baseNum) else: return(baseNum* power FunRecursive (base Num, expNum-1)) def powerFunIteration (baseNum, expNum): numPower = 1 for i in range(exp): numPower = numPower*base return numPower # main program base int(input("Enter number: ")) = exp = int(input("Enter exponent: ")) numPowerRecursion = power Fun Recursive(base, exp) print("Recursion: ", base, " raised to ", exp, numPowerIteration powerFunIteration (base, exp) = "I print( "Iteration: ", base, raised to ", exp, Enter number: 10 Enter exponent: 3 Recursion: 10 raised to 3 Iteration: 10 raised to 3 = 1000 = 1000 "I "I , numPowerRecursion) "I , numPowerIteration) Infinite Recursive Function You have to be very careful when implementing a recursive call, you must provide a way to stop repeating by finding a specific condition to avoid unlimited redundancy occurring. During infinite recursion, the system stops responding due to too many function calls, which leads to memory overflow and application termination. وزارة التعليم Ministry of Education 76 2024-1446

Exercises 1 Read the sentences and tick ✓ True or False. 1. Recursive functions have two states. 2 2. A recursive function calls another function. 3. Recursive functions are faster to execute. 4. Recursive calling functions makes the code block smaller. 5. Writing repetitive code requires less recursion. What are the differences between iteration and recursion? 3 When should recursion be used? وزارة التعليم Ministry of Education 2024-1446 True False 77

4 5 List the advantages and disadvantages of using recursion. Write a recursive Python function to calculate the nth largest number in a list. 6 Write a recursive Python function to calculate the sum of all the even numbers in a list. وزارة التعليم Ministry of Education 78 2024 -1446