Search icon CANCEL
Arrow left icon
Explore Products
Best Sellers
New Releases
Books
Videos
Audiobooks
Learning Hub
Conferences
Free Learning
Arrow right icon
Arrow up icon
GO TO TOP
Java 9 Data Structures and Algorithms

You're reading from   Java 9 Data Structures and Algorithms A step-by-step guide to data structures and algorithms

Arrow left icon
Product type Paperback
Published in Apr 2017
Publisher Packt
ISBN-13 9781785889349
Length 340 pages
Edition 1st Edition
Languages
Arrow right icon
Author (1):
Arrow left icon
Debasish Ray Chawdhuri Debasish Ray Chawdhuri
Author Profile Icon Debasish Ray Chawdhuri
Debasish Ray Chawdhuri
Arrow right icon
View More author details
Toc

Table of Contents (13) Chapters Close

Preface 1. Why Bother? – Basic FREE CHAPTER 2. Cogs and Pulleys – Building Blocks 3. Protocols – Abstract Data Types 4. Detour – Functional Programming 5. Efficient Searching – Binary Search and Sorting 6. Efficient Sorting – quicksort and mergesort 7. Concepts of Tree 8. More About Search – Search Trees and Hash Tables 9. Advanced General Purpose Data Structures 10. Concepts of Graph 11. Reactive Programming Index

Recursive algorithms

As I have already pointed out, recursive algorithms are a different way of thinking about solving a problem. For example, say our problem is to write a program that, given a positive integer n, returns the sum of numbers from zero to n. The known imperative way of writing it is simple:

public int sum_upto(int n){
  int sum=0;
  for(int i=0;i<=n;i++){
    sum+=i;
  }
  return sum;
}

The following would be the functional version of the problem:

public int sum_upto_functional(int n){
  return n==0?0:n+sum_upto_functional(n-1);
}

That's it–just a one-liner! This is probably nothing new to Java programmers, as they do understand recursive functions. However, an imperative programmer would use recursion only when nothing else worked. But this is a different way of thinking. How do we justify that it is equivalent to solving the problem for a smaller input and then composing it with something else? Well, we are certainly first computing the same function for an...

lock icon The rest of the chapter is locked
Register for a free Packt account to unlock a world of extra content!
A free Packt account unlocks extra newsletters, articles, discounted offers, and much more. Start advancing your knowledge today.
Unlock this book and the full library FREE for 7 days
Get unlimited access to 7000+ expert-authored eBooks and videos courses covering every tech area you can think of
Renews at $19.99/month. Cancel anytime