Algoritma dan Struktur Data : Rekursif dan Contoh Soal
Introduction to Recursion
A recursive process: one in which objects are defined in terms of other objects of the same type.
Droste Effect: is the effect of a picture appearing within itself, in a place where a similar picture would realistically be expected to appear
Visual Recursion
Recursive Pattern
Recursion in Computer Science
Recursion = Method
The solution to a problem depends on solutions to smaller instances of the same problem.
Two properties :
- A simple cases (base case, anchor)
- A set of rules which reduce all other cases toward the base case (recurrence)
Thinking Recursively
List of numbers : 23, 72, 56, 88, 30
Another list of numbers : 14 ; 23, 57, 20 ; 1, 2 ; etc.
Definition of a list of numbers :
- A List of Numbers is a : Number
- A List of Numbers is a : Number-comma-List of Numbers
The concept of List of Numbers is used to define itself !
Infinite Recursion
All recursive definition must have a non-recursive part
Without non-recursive part: no way to terminate the recursive path
Factorial
n!=1 ×2 ×3 ×…×n
n!=n ×(n-1)×(n-2)×…×1
n!=n ×(n-1)!
Recursive Definition of factorial :
Pseudocode
Analysis
Maximum in Array
Problem : Find the largest element in an Array of n elements, n >= 1
Example
Recursive definition :
Pseudocode
Analysis
Fibonacci Number
Fibonacci Sequence :
- Leonardo of Pisa a.k.a Fibonacci
- Growth of biologically unrealistic rabbit population
Recursive Definition :
Pseudocode
Analysis On Fibonacci Number
Sum of an Array
Problem : Find the sum of all elements in an Array of n elements, n >= 1
Recursive definition:
Pseudocode
Analysis
Implementation Using Java
Method Calls
Tail v.s. Non-tail Recursion
Non-Tail Recursion: Other Recursive methods which are not a tail recursion
Since the recursive call is the last action of the function, there is no need for recursion. Tail recursive methods are easy to convert to iterative. No difference in execution time for most compilers, smart compilers can detect and transform it into a iteration
When Not To Use Recursive
Recursive: elegant and easy
But, not all problems are solved efficiently using recursive.
Recursion tree: analyze the recursive call.
Chain recursion tree: a recursive call makes only one recursive call to itself
Transformation from recursion to iteration is often easy
Iterative can save both space and time.
Duplicate tasks in recursion tree: indication of time wasting to solve the same instance of a problem.
Look up table: never duplicate work by solving the same instance of a problem in separate recursive calls.
Example: Factorial & Fibonacci
Recursion v.s. Iteration
Every recursive function can be transformed into iterative function (or using Stack). Conversely, any iterative program that manipulates a stack can be replaced by a recursive program without a stack. Time complexity can be compared to identify when not to use recursion
In general, recursion needs more space & may cause stack overflow. But easier to design and more readable
Exercises
Create a recursive method/function to:
- multiply two integers, using only addition and recursion à MULT (a,b)
- compute the power of a number à POWER (a,n)
- compare two strings (identical or not) Ã STRCMP (s1,s2)
- check if a string is a palindrome à ISPALINDROME (S)
Sumber
Slide ASD : Rekursif
Posting Komentar