Algoritma Dan Struktur Data

Algoritma Dan Struktur Data Pendidikan Teknik Informatika

Algoritma dan Struktur Data : Rekursif dan Contoh Soal

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

Tail Recursion: it occurs when the last-executed statement of a function/method is a recursive call

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: