Scribd
Upload
3 views

Lecture 7 Recursive Function - General

A recursive function is one that calls itself, creating a chaining process. The document provides examples of recursive functions for calculating factorial, Fibonacci numbers, and the greatest common divisor (GCD), along with their definitions and termination conditions. It also includes a practice problem related to generating Legendre polynomials using recursion.

Uploaded by

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

Lecture 7 Recursive Function - General

A recursive function is one that calls itself, creating a chaining process. The document provides examples of recursive functions for calculating factorial, Fibonacci numbers, and the greatest common divisor (GCD), along with their definitions and termination conditions. It also includes a practice problem related to generating Legendre polynomials using recursion.

Uploaded by

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

Recursive Function

What is Recursive function?


v When a function calls itself, then the function
is called recursive function.
v A recursive function creates a process of
chaining.

Steps of Recursive Function


Ø Termination
Ø Reduction
Example 1 (Factorial)
#include <stdio.h> Chaining Process of Recursive Function

long Factorial(int n); /* function prototype */

main(){
int n;
long fvalue;

printf(“Enter a value: “);


scantf(“%d”, &n);

fvalue = Factorial(n); /* calling function */

printf(“The factorial of %d is %ld.”, n, fvalue);


return 0;
}

long Factorial(int n){ /* function definition */


if (n==1) return 1;
return n*Factorial(n-1);
}
Example 2 (Fibonacci Number)
1 1 2 3 5 8 13 21 ……
Output of Recursive Function

Recursive Definition:
1. Termination,
F1 = 1 and F2 = 1
2. Reduction.
Fn = Fn-1 + Fn-2

int Fab(int n){


if (n == 1 || n == 2) return 1;
return (Fab(n-1)+Fab(n-2));
}
Find gcd of 15 and 9.
Example 3 (GCD)
9 ) 15 ( 1
9
---------
6) 9 ( 1
6 int GCD(int a, int b){
---------
3)6(2 if (a % b == 0) return b;
6 return GCD(b, a%b);
------
}
Find gcd of a and b

Recursive Definition:
1. Termination,
if (a % b == 0) return b;
2. Reduction.
return gcd(b, a%b)
Practice
Problem 7.11(a) (Page 7.37)

The Legendre polynomials can be calculated by means of the formula


P0 = 1, P1 = x
Pn = [(2n-1)/n]xPn-1 – [(n-1)/n]Pn-2
Where n = 2, 3, 4, ….. and x is any floating-point number between -1 and
1. (Note that the Legendre polynomials are floating-point quantities).
Write a recursive function to generate nth Legendre polynomial term.
Let the values of n and x be input parameters.

main(){ float LP(int n, float x){


………………………………. ……………………………….
} }

You might also like