Introduction to algorithms and data structures & recursion (lecture 1)

1.

LECTURE 1 – INTRODUCTION TO
ALGORITHMS AND DATA STRUCTURES &
RECURSION (PART II)
Aigerim Aibatbek, Eldiyar Zhantileuov
[email protected], [email protected]

2.

CONTENT
1. Example 2 – Factorial of the Number
2. Iteration vs Recursion
3. How to create a recursive algorithm?
2

3.

EXAMPLE 2 – FACTORIAL OF THE NUMBER
Base case!
3

4.

EXAMPLE 2 – FACTORIAL SOLUTION
4

5.

ITERATION VS RECURSION
Repetition
• Iteration: explicit loop
• Recursion: repeated function calls
Termination
• Iteration: loop condition fails
• Recursion: base case recognized
Both can have infinite loops
Balance between performance (iteration) and
good software engineering (recursion)
5

6.

HOW TO CREATE A RECURSIVE ALGORITHM?
6

7.

LITERATURE
Algorithms, 4th Edition, by Robert Sedgewick and Kevin Wayne, Addison-Wesley
Chapter 1.1
Grokking Algorithms, by Aditya Y. Bhargava, Manning
Chapter 3
7

8.

GOOD LUCK!