[go: up one dir, main page]
Scribd
Upload
3 views2 pages

32 - Recursion

Recursion is a process where a function calls itself to solve smaller subproblems, and it is essential to define a base case to prevent infinite loops. Key properties include performing the same operations with different inputs and breaking down problems into simpler versions. The algorithm for implementing recursion involves defining a base case, a recursive case, ensuring termination, and combining solutions to solve the original problem.

Uploaded by

huzaifarasheed4567
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views2 pages

32 - Recursion

Recursion is a process where a function calls itself to solve smaller subproblems, and it is essential to define a base case to prevent infinite loops. Key properties include performing the same operations with different inputs and breaking down problems into simpler versions. The algorithm for implementing recursion involves defining a base case, a recursive case, ensuring termination, and combining solutions to solve the original problem.

Uploaded by

huzaifarasheed4567
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

Recursion

The process in which a function calls itself directly or indirectly is called


recursion and the corresponding function is called a recursive function. Using a
recursive algorithm, certain problems can be solved quite easily. Examples of
such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree
Traversals, DFS of Graph, etc. A recursive function solves a particular problem
by calling a copy of itself and solving smaller subproblems of the original
problems. Many more recursive calls can be generated as and when required. It is
essential to know that we should provide a certain case in order to terminate this
recursion process. So we can say that every time the function calls itself with a
simpler version of the original problem.

Properties of Recursion:
 Performing the same operations multiple times with different inputs.
 In every step, we try smaller inputs to make the problem smaller.
 Base condition is needed to stop the recursion otherwise infinite loop will
occur.

Algorithm: Steps
The algorithmic steps for implementing recursion in a function are as follows:

Step1 - Define a base case: Identify the simplest case for which the solution is
known or trivial. This is the stopping condition for the recursion, as it prevents
the function from infinitely calling itself.

Step2 - Define a recursive case: Define the problem in terms of smaller


subproblems. Break the problem down into smaller versions of itself, and call the
function recursively to solve each subproblem.

Step3 - Ensure the recursion terminates: Make sure that the recursive function
eventually reaches the base case, and does not enter an infinite loop.

step4 - Combine the solutions: Combine the solutions of the subproblems to solve
the original problem.
What is the base condition in recursion?
In the recursive program, the solution to the base case is provided and the
solution to the bigger problem is expressed in terms of smaller problems.

int fact(int n)
{
if (n < = 1) // base case
return 1;
else
return n*fact(n-1);
}
In the above example, the base case for n < = 1 is defined and the larger value of
a number can be solved by converting to a smaller one till the base case is
reached.

You might also like