P a g e |1
Recursion & Data Structures
Man is always seeking solutions to problems and is always also looking
for better solutions.
In computer science, there are different class of problems each requiring
different to problems solving techniques.
We have seen how we can use loops to solve some problems quite well.
Another approach to problem solutions is Recursion.
Recursion is a problem-solving technique that involves breaking a problem into
smaller instances of the same problem (also called subproblems) until we get
a small enough subproblem having a trivial solution.
We can say that recursion is “defining a problem in terms of itself” as it involves
a function calling itself with a base case to terminate the infinite loop.
Technically, recursion is a problem-solving technique where the ultimate
solution depends on solutions to smaller instances of the same problem.
The concept relys on the fact that a problem can be solved much easily and
in lesser time if it is represented in one or smaller versions.
Consider the mathematical expression y=x7
This can linearly be expressed as follows:
6
y=x.x
5
y=x.x.x .
4
y=X.x.x.x
3
y=X.X.x.x.x
2
y=X.X.X.x.x.x
1
y=X.X.X.X.x.x.x
Recursion in data structure
, P a g e |2
0
y=X.X.X.X.X.x.x.x
y=X.X.X.X.X.x.x.1
Iterative solution
Consider y=27 . Therefore X=2; the last term is Y0=1;
Let y=1;
for (int i=1;i<=7;i++){
y*=2;
}
Write the above in a method power (int x, int y)
Using Recursion to solve the above Power Problem
Recursive functions allow programmers to write efficient programs using a
minimal amount of code.
The downside is that they can cause infinite loops and other unexpected
results if not written properly.
For example, in the example above, the function is terminated if the number is 0 .
If proper cases are not included in a recursive function to stop the execution,
it will repeat forever, causing the program to crash or become unresponsive.
Therefore care must be taken when constructing a recursive algorithms.
Recursion in data structure
Recursion & Data Structures
Man is always seeking solutions to problems and is always also looking
for better solutions.
In computer science, there are different class of problems each requiring
different to problems solving techniques.
We have seen how we can use loops to solve some problems quite well.
Another approach to problem solutions is Recursion.
Recursion is a problem-solving technique that involves breaking a problem into
smaller instances of the same problem (also called subproblems) until we get
a small enough subproblem having a trivial solution.
We can say that recursion is “defining a problem in terms of itself” as it involves
a function calling itself with a base case to terminate the infinite loop.
Technically, recursion is a problem-solving technique where the ultimate
solution depends on solutions to smaller instances of the same problem.
The concept relys on the fact that a problem can be solved much easily and
in lesser time if it is represented in one or smaller versions.
Consider the mathematical expression y=x7
This can linearly be expressed as follows:
6
y=x.x
5
y=x.x.x .
4
y=X.x.x.x
3
y=X.X.x.x.x
2
y=X.X.X.x.x.x
1
y=X.X.X.X.x.x.x
Recursion in data structure
, P a g e |2
0
y=X.X.X.X.X.x.x.x
y=X.X.X.X.X.x.x.1
Iterative solution
Consider y=27 . Therefore X=2; the last term is Y0=1;
Let y=1;
for (int i=1;i<=7;i++){
y*=2;
}
Write the above in a method power (int x, int y)
Using Recursion to solve the above Power Problem
Recursive functions allow programmers to write efficient programs using a
minimal amount of code.
The downside is that they can cause infinite loops and other unexpected
results if not written properly.
For example, in the example above, the function is terminated if the number is 0 .
If proper cases are not included in a recursive function to stop the execution,
it will repeat forever, causing the program to crash or become unresponsive.
Therefore care must be taken when constructing a recursive algorithms.
Recursion in data structure
