ALGORITHMS AND DATA STRUCTURES
LECTURE 1 - RECURSION
Askar Khaimuldin
askar.khaimuldin@astanait.edu.kz
CONTENT
1. Recursion Overview
2. Simple example
3. How it works?
4. Function call and Stack
5. Iteration vs Recursion
6. How to create a recursive algorithm?
7. Fibonacci solution
RECURSION OVERVIEW
Recursion is the process of repeating items in a self-similar way
A way to design solutions by Divide-and-Conquer
Reduce a problem to simpler versions of the same problem
A programming technique where a function calls itself
Must have at least 1 base case
Base case means that there exist one or more inputs for which the function
produces a result trivially (without recurring)
Must solve the same problem on some other input with the goal of simplifying
the larger problem input
SIMPLE EXAMPLE
N! = 1•2•3•4•5•6•7•…•N fact(N)
N! = 1•2•3•4•5•6•7•…•(N-1) •N fact(N-1) * N
N! = 1•2•3•4•5•6•7•…•(N-2) •(N-1)•N fact(N-2) * (N-1) * N
N! = 1 •2•3•4•5•6•7•…•N fact(1) * 2 * 3 * … * N
Base case!
SIMPLE EXAMPLE
HOW IT WORKS?
Recursion is no different than a function call
Every function call creates a new frame (block) inside the stack
The system keeps track of the sequence of method calls that have been
started but not finished yet (active calls)
• order matters
Recursion pitfalls
• miss base-case (infinite recursion, stack overflow)
• no convergence (solve recursively a problem that is not simpler than the
original one)
FUNCTION CALL AND STACK
When you run a program, the computer creates a
stack for you
Each time you invoke a method, the method is placed
to the stack
A stack is a last-in/first-out memory structure. The
first item referenced or removed from a stack is
always the last item entered into the stack
If some function call has produced an excessively
long chain of recursive calls, it can lead to stack
overflow
ITERATION VS RECURSION
Iteration
• Uses repetition structures (for, while or do…while)
• Repetition through explicitly use of repetition structure
• Terminates when loop-continuation condition fails
• Controls repetition by using a counter
Recursion
• Uses selection structures (if, if…else or switch)
• Repetition through repeated method calls
• Terminates when base case is satisfied
• Controls repetition by dividing problem into simpler one
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)
HOW TO CREATE A
RECURSIVE ALGORITHM?
1. Think about a problem at a high level of abstraction
2. Figure out the base case for the program
3. Redefine the answer in terms of a simpler sub-
problem
4. Combine the results in the formulation of the answer
FIBONACCI SOLUTION
Fibonacci sequence Solution:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 …
Each element is the sum of previous two fib(n) = fib(n-2) + fib(n-1)
Starts from 0 and 1 fib(0) = 0 and fib(1) = 1 // this is a base case
Task: Find the Fibonacci number at the given
position
Example:
3rd element is 5
6th element is 8
LITERATURE
Algorithms, 4th Edition, by Robert Sedgewick and Kevin Wayne, Addison-Wesley
Chapter 1.1
Grokking Algorithms, by Aditya Y. Bhargava, Manning
Chapter 3
GOOD
LUCK!
