[go: up one dir, main page]
Scribd
Upload
9 views27 pages

L32 33 Recursion

Uploaded by

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

L32 33 Recursion

Uploaded by

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

Recursion

Divide-and-conquer
What is recursion?
Recursive functions
Nature of recursion
Nature of recursion
Types of Recursion
 Direct Recursion
 Indirect Recursion
Iteration vs. recursion
Recursion: sum()
Recursion: sum()
How does recursion
work?
How does recursion
work?
How does recursion
work?
Recursion
Recursive functions
 Functions that call themselves
 Can only solve a base case
 Divide a problem up into
● What it can do
● What it cannot do

 What it cannot do resembles original problem


 The function launches a new copy of itself (recursion step)
to solve what it cannot do
 Eventually base case gets solved
● Gets plugged in, works its way up and solves whole
problem
Recursion
Example: factorials
 5! = 5 * 4 * 3 * 2 * 1
 Notice that
● 5! = 5 * 4!
● 4! = 4 * 3! ...

 Can compute factorials recursively


 Solve base case (1! = 0! = 1) then plug
in
● 2! = 2 * 1! = 2 * 1 = 2;
● 3! = 3 * 2! = 3 * 2 = 6;
Recursion Final value = 120
5! 5!
5! = 5 * 24 = 120 is returned
5 * 4! 5 * 4!
4! = 4 * 6 = 24 is returned
4 * 3! 4 * 3!
3! = 3 * 2 = 6 is returned
3 * 2! 3 * 2!
2! = 2 * 1 = 2 is returned
2 * 1! 2 * 1!
1 returned
1 1

(a) Sequence of recursive calls. (b) Values returned from each recursive call.
1
2 Recursive factorial function */
3 #include <stdio.h>
4
5 long factorial( long number ); /* function prototype */
6
7 /* function main begins program execution */
8 int main()
9 {
10 int i; /* counter */
11
12 /* loop 10 times. During each iteration, calculate
13 factorial( i ) and display result */
14 for ( i = 1; i <= 10; i++ ) {
15 printf( "%2d! = %ld\n", i, factorial( i ) );
16 } /* end for */
17
18 return 0; /* indicates successful termination */
19
20 } /* end main */
22 /* recursive definition of function factorial */
23 long factorial( long number )
24 {
25 /* base case */
26 if ( number <= 1 ) {
27 return 1;
28 } /* end if */
29 else { /* recursive step */
30 return ( number * factorial( number - 1 ) );
31 } /* end else */
32
33 } /* end function factorial */
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
Recursion: The Fibonacci
Series
Fibonacci series: 0, 1, 1, 2, 3, 5, 8...
 Each number is the sum of the previous two
 Can be solved recursively:
● fib( n ) = fib( n - 1 ) + fib( n – 2 )
 Code for the fibonacci function
long fibonacci( long n )
{
if (n == 0 || n == 1) // base case
return n;
else
return fibonacci( n - 1) +
fibonacci( n – 2 );
}
Recursion: The Fibonacci
Series
f( 3 )

return f( 2 ) + f( 1 )

return f( 1 ) + f( 0 ) return 1

return 1 return 0
1
2 Recursive fibonacci function */
3 #include <stdio.h>
4
5 long fibonacci( long n ); /* function prototype */
6
7 /* function main begins program execution */
8 int main()
9 {
10 long result; /* fibonacci value */
11 long number; /* number input by user */
12
13 /* obtain integer from user */
14 printf( "Enter an integer: " );
15 scanf( "%ld", &number );
16
17 /* calculate fibonacci value for number input by user */
18 result = fibonacci( number );
19
20 /* display result */
21 printf( "Fibonacci( %ld ) = %ld\n", number, result );
22
27 /* Recursive definition of function fibonacci */
28 long fibonacci( long n )
29 {
30 /* base case */
31 if ( n == 0 || n == 1 ) {
32 return n;
33 } /* end if */
34 else { /* recursive step */
35 return fibonacci( n - 1 ) + fibonacci( n - 2 );
36 } /* end else */
37
38 } /* end function fibonacci */

Enter an integer: 0
Fibonacci( 0 ) = 0

Enter an integer: 1
Fibonacci( 1 ) = 1

Enter an integer: 2
Fibonacci( 2 ) = 1

Enter an integer: 3
Fibonacci( 3 ) = 2

Enter an integer: 4
Fibonacci( 4 ) = 3
Enter an integer: 5
Fibonacci( 5 ) = 5

Enter an integer: 6
Fibonacci( 6 ) = 8

Enter an integer: 10
Fibonacci( 10 ) = 55

Enter an integer: 20
Fibonacci( 20 ) = 6765

Enter an integer: 30
Fibonacci( 30 ) = 832040

Enter an integer: 35
Fibonacci( 35 ) = 9227465
Recursion vs.
Iteration
 Repetition
 Iteration: explicit loop
 Recursion: repeated function calls
 Termination
 Iteration: loop condition fails
 Recursion: base case recognized
 Both can have infinite loops
 Balance
 Choice between performance (iteration) and
good software engineering (recursion)
GCD

else
{
r=x%y;
return (recgcd(y,r));
}

Output:
Enter the two number 5 8
G.C.D. of the 5 and 8 is 1
Problems on recursion
 Factorial
 Fibonacci number generation
 Fibonacci series generation
 Reversing an integer number
 Calculating power of a number
 Prime Number checking
 Generating prime number series
 Calculating GCD of two numbers
 Generating table of a number

You might also like