Recursive Presentation

University Logo

Recursive Function

Presented by: Dr. Hazem AL-Najjar

Date 14/12/2021

Start

Learning Outcome

Learning Outcome 1 : Create recursive function to solve mathamtical problems

Activity to achieve LO: Write programs which contain recursive functions Desgin a solution Based on Recursive function

Tool : Slido Quiz Maker

Outlines

07. Solution of Previous Problems

04. Greatest Common Divisor

01. First Step

02. Factorial

05. Problems Solution

08. Advantages and Disadvantages

03. Fibonacci

06. Recusive

01. First Step : What is recursive

Made for solving problems that can be broken down into smaller, repetitive problems.

It is especially good for working on things that have many possible branches and are too complex for an iterative approach Trees and graphs are another time when recursion is the best and easiest way to do traversal.

02. First Problem: Factorial

The factorial of a nonnegative integer n, written n! (and pronounced “n factorial”), is the product n · (n – 1) · (n – 2) · … · 1

Recursive definition of the factorial functionn! = n · (n – 1)!

Example

03. Second Problem: The Fibonacci series

0, 1, 1, 2, 3, 5, 8, 13, 21, … Begins with 0 and 1 Each subsequent Fibonacci number is the sum of the previous two Fibonacci numbers

Formula

04. Third Problem: Greatest Common Divisor

Greatest Common Divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers x, y, the greatest common divisor of x and y is gcd(x,y) .

Question 1

STEP 1

STEP 2

STEP 3

STEP 4

STEP 5

05. Problems Solution

To solve the problem of repreating the same process again and again

Programmers suggested to use a recursive function to implement the previous program in computer . A function that is defined in terms of itself is called recursive

INFO

06. Recusive

A function that calls itself, either directly, or indirectly (through another function)

NOT BASE

BASE

int fun(int x) { if (x==0) --> Base return 0; else return 2*fun(x-1)+x*x; }

Rules

05. Example of fun()

int fun(int x) { if (x==0) return 0; else return 2*fun(x-1)+x*x; }

Fun

Slido.co

A correct recursive function

int sum(int n) { if (n==0) return 0; else return n+sum(n-1); } void main() { cout<<sum(3); }

• You Must insure that you have Base case and other case.
• Insure that the recursive will be terminated.

Slido

07. Factorial Solution

int factorial(int n) { if ( n==0 ) / / base case return 1; else // recursive step return n*factorial(n - 1); } void main() { int i; // Loop 5 times. During each iteration, calculate // factorial( i ) and display result. for ( i = 0; i <= 5; i++ ) cout << i << "! = "<< factorial( i ) << endl; }

07. Fibonacci Solution

long fibonacci(long n) { if (n==0||n == 1) return n; else return fibonacci(n-1) + fibonacci( n-2); } int main() { cout<<"Hello World"<<endl; cout<<fibonacci(20); return 0; }

Formula

07. Greatest Common Divisor Solution

int GCD_Rec(int num1, int num2) { if (num2 != 0) { return GCD_Rec( num2, num1 % num2); } else { return num1; } }

08. Advantages and Disadvantages of Recursion

Disadvantges

Advantges

Thanks for your attention

Any question?