All categories

4 years ago

Is recursion ever required to solve a problem? What other approach can you use to solve a problem that is repetitive in nature?

Computers and Technology

1 answer:

Setler79 [48]4 years ago

8 0

Answer:

No you can not tell that recursion is ever required to solve a problem.

Recursion is required when in the problem, the solution of the input depends on the solution of the subsets of the input.

Iteration is also another form of repetitive approach we follow to solve that kind of problems.

But the difference between recursion and iteration is :

In recursion we call the function repeatedly to return the result to next level.
In iteration certain bunch of instructions in a loop are executed until certain conditions met.

Explanation:

For example in the Fibonacci sequence problem, to find $f_{n}$ , we need to compute $f_{n-1}$ and $f_{n-2}$ before that.

In case of recursion we just call the method Fibonacci(n) repeatedly only changing the parameter Fibonacci(n-1), that calculates the value and return it.

Fibonacci(n)

1. if(n==0 or n==1)

2. return 1.

3.else

4. return( Fibonacci(n-1)+Fibonacci(n-1) )

But in case of iteration we run a loop for i=2 to n, within which we add the value of current $f_{i-1}$ and $f_{i-2}$ to find the value of $f_{i}$

Fibonacci(n)

1. if(n<=2)

2. result = 1

3. else

4. result1 =1 and result2=1.

5. { result = result1 +result2.

6. result1= result2.

7. result2 = result.

8. }

9. output result.

You might be interested in

Bernard has a visual disability. Which type of assistive technology would he use to access print on the chalkboard or overhead s

dusya [7]

Answer:

a tactile input device

Explanation:

Based on the scenario being described it can be said that the best assistive technology for Bernard would be a tactile input device. Such a device would allow Bernard to physically interact with the print on the chalkboard or overhead screen from the device itself without having to actually get close to the chalkboard or screen. Thus allowing him to view its content from the palm of his hand.

8 0

3 years ago

A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S. For example, if S is 5,15,-30,10,-5,

Sindrei [870]

Answer:

We made use of the dynamic programming method to solve a linear-time algorithm which is given below in the explanation section.

Explanation:

Solution

(1) By making use of the dynamic programming, we can solve the problem in linear time.

Now,

We consider a linear number of sub-problems, each of which can be solved using previously solved sub-problems in constant time, this giving a running time of O(n)

Let G[t] represent the sum of a maximum sum contiguous sub-sequence ending exactly at index t

Thus, given that:

G[t+1] = max{G[t] + A[t+1] ,A[t+1] } (for all 1<=t<= n-1)

Then,

G[0] = A[0].

Using the above recurrence relation, we can compute the sum of the optimal sub sequence for array A, which would just be the maximum over G[i] for 0 <= i<= n-1.

However, we are required to output the starting and ending indices of an optimal sub-sequence, we would use another array V where V[i] would store the starting index for a maximum sum contiguous sub sequence ending at index i.

Now the algorithm would be:

Create arrays G and V each of size n.

G[0] = A[0];

V[0] = 0;

max = G[0];

max_start = 0, max_end = 0;

For i going from 1 to n-1:

// We know that G[i] = max { G[i-1] + A[i], A[i] .

If ( G[i-1] > 0)

G[i] = G[i-1] + A[i];

V[i] = V[i-1];

Else

G[i] = A[i];

V[i] = i;

If ( G[i] > max)

max_start = V[i];

max_end = i;

max = G[i];

EndFor.

Output max_start and max_end.

The above algorithm takes O(n) time .

4 0

3 years ago

The___is a waterproof fabric that is placed around your camera

Zina [86]

Can you help me with homework and the answer is a circle

5 0

3 years ago

Problem Statement − Suppose the problem statement at hand is to contain the attrition that happens in companies worldwide. High

Tju [1.3M]

Answer:Analysis is derived from the Greek word ‘analusis’, which translates into ‘breaking up’ in English. Analysis is older than the times of great philosophers like Aristotle and Plato. As discussed in the previous section, analysis is the process of breaking down a big single entity into multiple fragments. It is a deduction where a bigger concept is broken down to smaller ones. This breaking down into smaller fragments is necessary for improved understanding.

So, how does analysis help in design thinking? During analysis, design thinkers are required to break down the problem statement into smaller parts and study each one of them separately. The different smaller components of the problem statement are to be solved one-by-one, if possible. Then, solutions are thought for each of the small problems. Brainstorming is done over each of the solutions.

Later, a feasibility check is done to include the feasible and viable solutions. The solutions that don’t stand firm on the grounds of feasibility and viability are excluded from the set of solutions to be considered.

Design thinkers are, then, encouraged to connect with the diverse ideas and examine the way each idea was composed. This process of breaking down the bigger problem statement at hand into multiple smaller problem statements and examining each as a separate entity is called analysis.

Reductionism

The underlying assumption in analysis is reductionism. Reductionism states that the reality around us can be reduced down to invisible parts. The embodiment of this principle is found in basic axioms of analytic geometry, which says “the whole is equal to the sum of its parts”. However, understanding of a system cannot be developed by analysis alone. Hence, synthesis is required following analysis.

Synthesis

Synthesis refers to the process of combining the fragmented parts into an aggregated whole. It is an activity that is done at the end of the scientific or creative inquiry. This process leads to creation of a coherent bigger entity, which is something new and fresh. How does synthesis come into picture in design thinking?

Once the design thinkers have excluded the non-feasible and non-viable solutions and have zeroed-in on the set of feasible and viable solutions, it is time for the thinkers to put together their solutions.

Out of 10 available solutions, around 2-3 solutions may need to be excluded since they may not fit into the larger picture, i.e. the actual solution. This is where synthesis helps.

The design thinkers start from a big entity called the problem statement and then end up with another bigger entity, i.e. the solution. The solution is completely different from the problem statement. During synthesis, it is ensured that the different ideas are in sync with each other and do not lead to conflicts.

Analysis + Synthesis = Design Thinking

Analysis and synthesis, thus, form the two fundamental tasks to be done in design thinking. Design thinking process starts with reductionism, where the problem statement is broken down into smaller fragments. Each fragment is brainstormed over by the team of thinkers, and the different smaller solutions are then put together to form a coherent final solution. Let us take a look at an example.

Analysis Synthesis

Case Study

Problem Statement − Suppose the problem statement at hand is to contain the attrition that happens in companies worldwide. High quality employees leave the organization, mainly after the appraisal cycle. As a result, an average company loses its valuable human resources and suffers from overhead of transferring the knowledge to a new employee. This takes time and additional human resource in the form of a trainer, which adds to the company’s costs. Devise a plan to contain attrition in the company.

Analysis − Now, let’s break down the problem statement into various constituent parts. Following are the subparts of the same problem statement, broken down to elementary levels.

The employees are not motivated anymore to work in the company.

Appraisal cycle has something to do with attrition.

Knowledge transfer is necessary for new employees.

Knowledge transfer adds to the cost of the company.

Synthesis − Now, let's start solving each problem individually. In this step, we will do synthesis. Let's look at one problem at a time and try to find a solution only for that problem statement, without thinking of other problem statements.

Explanation:

6 0

3 years ago

Type the correct answer in the box. Spell all words correctly. Complete the sentence based on the role education plays to help y

CaHeK987 [17]

Answer:

what do i do??

Explanation:

8 0

3 years ago