Recursions

Briefly describe the concept of recursion in Computer Science by

○ Providing a definition of recursion in your own words;

○ Providing an example and explaining how it works;

○ Explaining what is the base case and recursive case of the example given.

ecursion in your own words:

Recursion is a concept in programming that involves breaking down large problems into

smaller subproblems which are of the same kind as the original problem and simpler to

solve. We will keep breaking these problems down into small enough problems where

you can solve it using the same algorithm without further reductions (this is considered

the base case).

Example:

If I want to calculate the value of N!, we can do this recursively by doing something as

such:

Def factorial_recursion(n: int) -> int:

If n <= 1:

Return 1

Return n * (factorial_recursion(n-1)

Explanation of Base and Recursive Case:

The base case of this recursive function would be if n is equal to 1 or 0, since any number

multiplied by 1 will simply evaluate to the same number.

The recursive case will be when we return n * (factorial_recursion(n-1)), where this will

calculate the final result of the factorial of the given input. It is also recursive in a sense

that we are “breaking down” the problem into smaller problems, where we are constantly

reducing the value of n by 1.

Contrast the operation of recursion and iteration in Computer Science. Analyze

the advantages and disadvantages of using recursion over iteration in Computer

Science. Provide an example and explain the reasoning behind your answers.

Recursion is the concept in programming that involves breaking down large problems into

smaller problems which are of the same kind as the original problem and simpler to solve.

This process of “breaking down” problems into smaller subproblems involves the function

calling itself inside of itself.

On the other hand, iteration is the process of solving a problem using a predetermined

set of instructions until a specific case or scenario is reached. When this specific case or

scenario is reached, the problem is solved.

The big difference between iteration and recursion is that iterations usually use some kind

of loop (while loop, for loop), while recursion solves problems by calling itself recursively.

For some people, the concept of iteration may be more intuitive to understand while for

some people recursion may be a bit more intuitive to understand.

Advantages of Iteration:

- The usage of iteration to solve problems costs less memory than recursive calls,

as we do not need to store the states of the previous function calls in the call

stack.

- There is no possibility of a stack overflow error as we are not storing a lot of stuff

in the stack call.

Disadvantages:

- The code used to solve a problem are usually less concise and less readable

compared to recursive code

Advantages of Recursion:

- The usage of recursion to solve problems usually lead to more concise and

readable code

- The code used to solve problems recursively are often times simpler than iterative

code

Disadvantages:

- Costs more memory than iterative calls as we need to store the states of previous

function calls in the call stack

- May run into stack overflow error when the recursion depth is too high

Can a recursive function be reimplemented by means of iteration? If yes, how?

Give an example.

Yes it can, as long as we can identify the base case of the recursive function and its

recurrence relation, we can convert a recursive function to an iterative function. In most

cases, the base case used for recursion will be used as the conditionals for the loops we

will use for iterations. For example, if we were to take the same function to calculate the

factorial of N and do it iteratively, the code will look like such:

Def factorial_iteration(n):

Sum = 1

While n > 1:

sum*=n

n-=1

Return sum

Comparing it to the recursive method, we see that the loop condition is when N is bigger

than 1, which is just the inverse of the recursion base case.

Can an iterative function be reimplemented by means of recursion? If yes, how?

Give an example.

Yes, an iterative function can be implemented by means of recursion. To do so, we will

need to identify the recurrence relation and also the base case. If we were to once again

take an example of finding the factorial of N, we can get the base case and recurrence

relation as such:

Base Case: N <= 1

Recurrence Relation: N N-1 N-2 … 1

Then, if we were to code it out we would get something like

Def factorial_recursion(n):

If n <= 1:

Return 1

Return n * factorial_recursion(n-1

Briefly describe the concept of tail recursion by

○ Providing an example and explaining how it works;

○ Describing how tail recursion works and how it differs from regular

recursion.

What is tail recursion: Tail recursion is a special form of recursion where the last

operation done in the function is its own recursive call. This means that the function

returns the output or the result directly without the need of further computation. This is

important as some languages can leverage this form of recursion in order to optimize

memory usage.

How is it different?

Tail recursion is different from normal recursion as normal recursion can have extra

operations done before fully returning the result. As an example, a normal recursion to

calculate the factorial of N might do something like N * factorial(N). But, tail recursion

might only have something like return factorial(N-1, N*sum).

This causes tail recursion to have better memory efficiency as we do not need to traverse

backwards (to finish calculating the previous function calls)

It is not tail recursive as the function still requires extra computation steps before fully

returning the value (return mystery(a, r) + (mystery(b, r))

One way you can make it tail recursive is by doing all the calculations in the function, so

doing something like

The purpose of this function is to calculate the value of every index with a difference of 2

starting from index 0. In other words, it will add up the value of elements in index 0, index

2, index 4, and so on until we reach the end of the list

The base case for this function is when the list is empty (len(arr) == 0)

It is not tail recursive as we still need to do extra computation at the end of the function,

which is to sum up all the elements that we’ve retrieved.

The output for the list [1, 2, 3, 4, 5, 6, 7, 8] would be 1 + 3 + 5 + 7 = 16

The function recurses by adding the first element of the list and calling itself by removing

the 2 front elements of the list. This process will be repeated until the length of the list

reaches 0 or there are no more elements in the list, returning the total sum of all

elements.

Def mystery(arr):

Index = 0

Ret = 0

While index >= len(arr):

ret+=arr[index]

index+=2

Return Ret

Best case and Worst case of O(N^2)

- N is number of elements in the list

This is because there will be N depth of recursive calls and also a cost of list slicing of

O(N), giving us a complexity of O(N * N) which is O(N^2)