Scribd
Upload
5 views17 pages

Recursion

The document discusses recursion as a technique for solving problems by breaking them down into smaller subproblems of the same type. It outlines the requirements for a recursive solution, including base cases and strategies for problem splitting and combining results. Additionally, it provides examples of recursive implementations for tasks such as printing messages, calculating factorials, summing arrays, generating Fibonacci numbers, and searching files recursively.

Uploaded by

usmana5664
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
5 views17 pages

Recursion

The document discusses recursion as a technique for solving problems by breaking them down into smaller subproblems of the same type. It outlines the requirements for a recursive solution, including base cases and strategies for problem splitting and combining results. Additionally, it provides examples of recursive implementations for tasks such as printing messages, calculating factorials, summing arrays, generating Fibonacci numbers, and searching files recursively.

Uploaded by

usmana5664
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

Introduction

Introduction (Cont.)
• Recursion is a technique that solves a problem by solving
a smaller problem of the same type

• In recursion a method call itself repeatedly to solve a


specific problem
Requirements for Recursive Solution

• At least one “small” case that you can solve directly

• A way of breaking a larger problem down into:


• One or more smaller subproblems
• Each of the same kind as the original

• A way of combining subproblem results into an overall


solution to the larger problem
General Recursive Design Strategy
• Identify the base case(s) (for direct solution)

• Devise a problem splitting strategy


• Subproblems must be smaller
• Subproblems must work towards a base case

• Devise a solution combining strategy


Recursive Hello World!
Let's try to write a recursive hello world
void print_recursive(int n)
{
if (n<=0)
return;
else {
cout<<n<<"-Hello World"<<endl;
print(n-1);

}
}

int main ()
{
print_recursive(10);
return 0;
}
Factorial
Recursive Factorial

A recursion trace for the call recursiveFactorial(4)


Array Sum
• we are given an array, A, of n integers that we want to
sum together using recursion!
Array Sum
• we are given an array, A, of n integers that we want to
sum together using recursion!
Recursion trace for an execution of LinearSum(A,n) with input parameters
A = {4,3,6,2,5} and n = 5.
Fibonacci Series
Recursive Fibonacci
1. Write a code to calculate nth Fibonacci series element

1. Now write a recursive implementation to do the same


task
Recursive Fibonacci
int fib(int n)
{
if (n == 0)
return 0;
if (n == 1)
return 1;
return fib(n-1)+fib(n-2);
}

Exercise: Draw recursion tree for fib(4)


Search a file in a folder recursively
Consider a scenario where you need to implement
a function to search for a specific file within a folder.
The folder may contain multiple subfolders, and the
depth of these subfolders is unknown.
Binary Search
• Given a sorted array of length n, find an element by value.
Iterative Binary Search
Recursive Binary Search

You might also like