SLC21 Week4 - Recursia

Greetings Steemit friends

1) Describe recursion as you understand it. Have you encountered recursion before? How is the word "fractal" related to recursion?

Recursion in programming is where a function is called to perform a small mathematical operation of a large problem. The operation only stops when the process reaches the base case, which is the stopping point. A good example different from that of the course is the recursive sum of numbers. Here the problem is broken into the base case and the recursive case. The base case is when n is equal to zero and the process has to stop, or the function continues to perform its operations until it gets to the endpoint.

We have a function to calculate the sum of the numbers from n.

int sumN(int n) {
if (n == 0) {
// Base case
return 0;
} else {
// Recursive case
return n + sumN(n - 1);
}
}

• Case n= 5

sumN(5) = returns 5 +sumN(4)
sumN(4) = returns 4 +sumN(3)
sumN(3) = returns 3 +sumN(2)
sumN(2) = returns 2 +sumN(2)
sumN(1) = returns 1 +sumN(0)
sumN(0) = returns 0 (Base case)

Yeah, I have encountered recursion in carrying out mathematical problems.

A Fractal is a pattern that looks the same at different scales. A recursive function is a fractal, performing the same process to smaller parts. Fractals are the visual look of the recursive function, which can still lead to an infinitely complex pattern.

2) Explore the limit of what is the largest value of the factorial that can be calculated with a certain type of data.

Talking about the limits of a large value are also determined by the data type, which we have come across in previous lessons. For a factorial case, we must consider the maximum value a data type can hold. So as soon as the value exceeds the data type maximum value, we have reached our limit for the data type.

We need to understand that the different data types have different ranges depending on their size in bytes, while data types like floats and doubles can handle larger ranges.

Factorial of numbers is faster, and can easily meet the range limit of a data type. So iterate factorial( n ), we have the larger n. Different data types hold their specific allocated memory size.

• Char (8bit) storing values with the range 0 to 255(unsigned) and -128 to 127(signed)
• Int (32-bit) storing values within the range of 2,147,483,648 to 2,147,483,647 (signed).
• Long (64-bit) storing values within the range 9,223,372,036,854,775,807 (signed).
• Long long (larger 64-bit) storing value within the range 18,446,744,073,709,551,615.

To get our largest value for n, will be the larger n! Within the range (255) for char(8-bit) and so on for the other data type.

n!=n×(n−1)!
1!=1,2!=2,3!=6,4!=24,5!=120, 6!=720 ......

In the case of 6!=720, it goes beyond and exceeds the range of 255. So the largest value for n! for the datatype (char(8bit)) is 120.

To handle other data types such as int (32-bit) and long (64-bit). The largest value will be that of n=12 and that of long will be n=20. We can't go beyond these n values because our return will exceed the maximum range.

Investigate how many calls the function will make before terminating.

Getting the number of calls before getting to the base case (endpoint) of a recursive function. We need to follow the fractal pattern of the recursive factorial function. Each recursive subtracts 1 from n to run another function call.

So we start counting from the first recursion, which starts with n and decreases by 1. So counting the number of fractions plus the base case, when n=0.

n=5

Function count

factorial(5) -> factorial(4) -> factorial(3) -> factorial(2) ->factorial(1) -> factorial(0)

Total calls : 5 + 1 = 6
Not the 1 is the base case.

4) Print numbers from 1 to n.

To print numbers from 1 to n, we achieve this by either creating a recursive function or using a for loop to iterate from 1 to n. For the sake of the course, we will print the numbers using the recursive function. With this method, we can easily match Mathematica's definition of recursion and when to stop.

We start by creating the recursive function, which will print the number from current to n. The parameter current tracks the current number printed, while n is the limit of the numbers to be printed. To complete our recursive function, the last call made is to check whether when the current exceeds n to stop the recursive(base case). The recursive call in our function purpose is to add 1 to the current and call the function again. Each call prints the next number until we get to the point where the number is greater than n.

In my case, I have set my upper limit for the number to be printed at 10 (n=10). The recursive function will start printing from 1 and continue up to n (10). Note my recursive function stops when the number to be printed is greater than 10.

For this case above, we can count a total of 11 recursive calls.
first current =1, print 1 ...... tenth call current =10, print 10 .
the next call printNumbers(11, 10), which returns true for the base case and stops the recursion.

5)Print numbers from n to 1.

Now we have to verify the order of printing numbers. Here our base case will be if n < 1, to stop the recursion calls. This time, the recursive call will decrement of n by and print itself before the next recursive call.

Maintain the same value of n=10.

first call printNumbers(10), print 10 and then call printNumbers(9).
second call printNumbers(9), print 9 and and then call printNumbers(8).

This will go on to eleven call printNumbers(0), which is the base case, and stop any recursion.

6) Write a function to calculate the sum of two numbers a+b. Do not use the a+b calculation directly. First, perform this task using a loop (1 point), maybe it will tell you how to use recursion here and perform this task (1 point)

Adding two numbers using a loop can be done without directly using the + operator. For the case of a+b, we can loop b time. By doing so add 1 to a until b iterates and ends the loop.

Two ways can start by creating a function to handle the loop or a direct approach. Best practice, a function is good.

In the function, initialize the variable result with the value a. Run the loop b times, with each interaction adding 1 to the result. At the point where we have iteration b time, the loop will stop and return the final result for a+b.

---

Using recursive, we have a base case and recursive call. Here, recursion will stop when b = 0 and a returns the result which is the base case.

In the recursive call, each recursive will add 1 to a and subtract 1 from b. if b is not equal to 0, the next recursive call is made. it goes on until b= 0 and a = result.

The final return value is the result for a+b by recursive,

7)

Previous class, we had a look at manipulating an array of string characters that is terminated by a null character.

char s[]="recursia";

The variable s represents the array address of the first character r, and *s (dereferences s) also hold the value stored at the address s point to which is r. Both s and *s will represent the first character r and *(s+1) will represent the second character e.

Here to represent the first character of an array, we can use either the index or the pointer arithmetic. (s[i] equivalent to *(s=1).

• Example using indexing:

the loop start at i =0, and each iteration print the character s[i] until it get to the null character (\0)

• Example using pointer:

The pointer s is passed to the function, which is then checked by a while loop if the address (*s) is not a null character. Each iteration prints the character, and an increase is executed on the pointer for the next memory location.

For both cases, the null character ends the loop and tells the end of the string. Both indexing and pointers virtually do the same operations.

8) Similar to the previous task - but the line must be displayed backwards, turned around.

Okay, now we will reverse the string operation using both the indexing and pointers. We have our string stored in the memory as r e c u r s i a. To be able to reverse a string, we need the length which is the logical size to be able to locate the last character. From one of our classes, we look at taking off the last character. For this case we will print each character, starting from the last and moving toward the first character.

• Example Using indexing

We used a while loop to start from the index 0 until stopped when s[length] == '\0' (null character), Print the character in reverse by looping backward (i--). Each character is printed using s[i] until index 0.

• Example using pointer

We used the while loop in this case to look for the end of the string. Each iteration increments the pointer until it points to a null character. At the end of the loop, we have the endpoint with the last character as end -1. Now printing in reverse is achieved by decrementing the pointer (end --) to get to the next last character. *end dereference the pointer get the character of the memory location and continue backward until the pointer gets to the starting address (s)

---

---

Cheers
Thanks for dropping by
@fombae