[go: up one dir, main page]
Scribd
Upload
14 views16 pages

Lecture - 8 - Recursion - REH

Uploaded by

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

Lecture - 8 - Recursion - REH

Uploaded by

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

Data Structure

Recursive Function

Rehnuma Haque
Lecturer, Department of CSE
Recursion
› Recursion is the process which comes into existence when a function calls a
copy of itself to work on a smaller problem.
› Any function which calls itself is called recursive function, and such
function calls are called recursive calls.
› Recursion involves several numbers of recursive calls. However, it is
important to impose a termination condition of recursion.
› For Example, recursion may be applied to sorting, searching, and traversal
problems.
Recursion
› Generally, iterative solutions are more efficient than recursion since
function call is always overhead.
› Any problem that can be solved recursively, can also be solved iteratively.
However, some problems are best suited to be solved by the recursion, for
example, tower of Hanoi, Fibonacci series, factorial finding, etc.
Recursion
› Recursion contains two cases in its program body.
› Base case: When you write a recursive method or function, it keeps calling
itself, so the base case is a specific condition in the function. When it is met,
it terminates the recursion. It is used to make sure that the program will
terminate. Otherwise, it goes into an infinite loop.
› Recursive case: The part of code inside the recursive function executed
repeatedly while calling the recursive function is known as the recursive
case.
Basic Syntax of Recursion
void recursive_fun() //recursive function
{
Base_case; // Stopping Condition
recursive_fun(); //recursive call
}
int main()
{
recursive_fun(); //function call
}
Basic Syntax of Recursion
› The function call inside the main function is normal call, it calls
the recursive_fun() function
› Inside the recursive_fun() function, there is another function call
named recursive_fun(); which is termed as a recursive call
› And the whole recursive_fun() function is recursive function.
› Base_case is the stopping condition for the recursive function.
Types of Recursion
› There are two types of recursion in C language:

› Direct Recursion: Direct recursion in C occurs when a function calls itself


directly from inside. Such functions are also called direct recursive functions.

› Indirect Recursion: Indirect recursion in C occurs when a function calls another


function and if this function calls the first function again.
Direct Recursion Example

function_1()
{
//some code
function_1();
//some code
}
Indirect Recursion Example
function_1()
{
//some code
function_2( );
}
function_2()
{
//some code
function_1( );
}
Example: Factorial
Two well-defined properties of a recursive
procedure are:
1. There must be certain base criteria for which the procedure does not
call itself.
2. Each time the procedure does call itself, it must be closer to the
base criteria.
Calculate 4!
• Example:
# Factorial Function 1. 4! = 4 .
3!
2 3! = 3 . 2!
(a) If n = 0, then n! = 1
. 2! = 2 . 1!
(b) If n > 0, then n! = n. 3 1! = 1. 0!
(n-1)! . 0! = 1
4 1! = 1 . 1
. =1
5 2! = 2 . 1 = 2
. 4! = 4 3!
9. . 6==3 . 2 = 6
6
24
.
Result: 4! =
Example: Factorial
Fibonacci Series
[ 0 1 1 2 3 5 8 13 21 34 55...]

• The Fibonacci Sequence is the series of numbers:


0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 54,...

• The next number is found by adding up the two numbers


before it:

the 2 is found by adding the two numbers before it (1+1),


the 3 is found by adding the two numbers before it (1+2),
the 5 is (2+3),
and so on!
Example: Fibonacci Series
Advantages of Recursion

› Advantages:
▪ The code becomes shorter and reduces the unnecessary calling to functions.
▪ Useful for solving formula-based problems and complex algorithms.
▪ Useful in Graph and Tree traversal as they are inherently recursive.
▪ Recursion helps to divide the problem into sub-problems and then solve them,
essentially divide and conquer.
Disadvantages of Recursion
› Disadvantages:
▪ The code becomes hard to understand and analyze.
▪ A lot of memory is used to hold the copies of recursive functions in the
memory.
▪ Time and Space complexity is increased.
▪ Recursion is generally slower than iteration
THE
END

You might also like