[go: up one dir, main page]
Scribd
Upload
153 views14 pages

Recursion: CCC121 - Data Structures and Algorithms

The document discusses recursion, defining it as solving a problem by reducing it to smaller versions of itself. It notes that every recursive definition must have a base case, which directly provides the solution, stopping further recursion. The general case reduces the problem further. An example of finding the factorial of 5 recursively is provided, showing how it breaks down into smaller subproblems until reaching the base cases of 0! = 1 and 1! = 1. Pros and cons are outlined, with recursion using more memory but being practical for some problems like tree traversals.

Uploaded by

Joshua Madula
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
153 views14 pages

Recursion: CCC121 - Data Structures and Algorithms

The document discusses recursion, defining it as solving a problem by reducing it to smaller versions of itself. It notes that every recursive definition must have a base case, which directly provides the solution, stopping further recursion. The general case reduces the problem further. An example of finding the factorial of 5 recursively is provided, showing how it breaks down into smaller subproblems until reaching the base cases of 0! = 1 and 1! = 1. Pros and cons are outlined, with recursion using more memory but being practical for some problems like tree traversals.

Uploaded by

Joshua Madula
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/ 14

Recursion

CCC121 – Data Structures and Algorithms


Discussions

Recursive
01 • Definition
• Base case and General Case
• Direct and Indirect Recursion

02 Recursive Algorithm
• Recursive functions
• Recursion vs. Iterations
Recursive Definition (Cont)

Definition

• Recursion: solving a problem by reducing it to smaller versions of itself.


• Provides a powerful way to solve certain problems which would be
complicated otherwise.
• Base case: the case for which the solution is obtained directly
• Every recursive definition must have one (or more) base case(s)
• The base case stops the recursion
• General case: must eventually reduce to a base case
Example

Factorials

• Factorials
0! = 1 (1)
n! = n x (n-1)! If n>0 (2)

• Equation (1) is called the base case


• Equation (2) is called the general or recursive case
Example

Find 5!

5! = Five factorial = 1 * 2 * 3 * 4 * 5 = 120

Notes: 0! = 1
1! = 1

Let’s find an algorithm to find factorial for any number: n!


An Iterative Algorithm

The Iterative solution uses a loop, and computes as it goes.

function getFactorial (5)


factorial = 1
for x = 1 to 5
factorial = factorial * x
A Recursive Algorithm

A recursive function breaks the problem down into smaller problem,


and calls itself for each of the smaller problems.

It includes a base case (or terminal case) and a recursive case.

5! = 5 * 4 * 3 * 2 * 1
A Recursive Algorithm

A recursive function breaks the problem down into smaller problem,


and calls itself for each of the smaller problems.

It includes a base case (or terminal case) and a recursive case.

5! = 5 * 4 * 3 * 2 * 1 4! = 4 * 3 * 2 * 1 Base case:
= 5 * 4! = 4 * 3! 0! = 1
1! = 1
A Recursive Algorithm
A Recursive Algorithm
A Recursive Algorithm

function getFactorial (n)


if n < 2, return 1
else return n * getFactorial(n-1)
Recursion Pros & Cons

Typically no calculations are done until the base case is reached.


So for very large problems (millions of recursive calls) you may run
out of memory since you’ll have millions of open function.
Recursion Pros & Cons

Con: does not scale up like iteration. Requires more memory

Con: in many languages iterative solutions are way faster

Con: sometimes more abstract or harder to understand than iterative solutions

Pro: in some cases, extremely fast and easy to code. Practical for tree traversals
and binary search.
END OF PRESENTATION

You might also like