DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports
Events Video Library
Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
View Events Video Library
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

Migrate, Modernize and Build Java Web Apps on Azure: This live workshop will cover methods to enhance Java application development workflow.

Modern Digital Website Security: Prepare to face any form of malicious web activity and enable your sites to optimally serve your customers.

Kubernetes in the Enterprise: The latest expert insights on scaling, serverless, Kubernetes-powered AI, cluster security, FinOps, and more.

A Guide to Continuous Integration and Deployment: Learn the fundamentals and understand the use of CI/CD in your apps.

Related

  • Reading an HTML File, Parsing It and Converting It to a PDF File With the Pdfbox Library
  • A Maven Story
  • JPA Criteria With Pagination
  • Ways To Reduce JVM Docker Image Size

Trending

  • Data Ingestion for Batch/Near Real-Time Analytics
  • What Is CI/CD? Beginner’s Guide To Continuous Integration and Deployments
  • Unveiling the Application Modernization Roadmap: A Swift and Secure Journey to the Cloud
  • Amazon EC2 Deep Dive: Optimizing Workloads With Hardware Insights
  1. DZone
  2. Coding
  3. Java
  4. Do it in Java 8: Recursive lambdas

Do it in Java 8: Recursive lambdas

Pierre-Yves Saumont user avatar by
Pierre-Yves Saumont
·
Mar. 06, 15 · Interview
Like (3)
Save
Tweet
Share
33.3K Views

Join the DZone community and get the full member experience.

Join For Free

Searching on the Internet about recursive lambdas, I found no relevant information. Only very old post talking about how to create recursive lambdas in ways that don't work with final version of Java8, or more recent (two years old only) post explaining this possibility had been remove from the JSR specification in October 2012, because “it was felt that there was too much work involved to be worth supporting a corner-case with a simple workaround.”

Although it might have been removed from the spec, it  is perfectly possible to create recursive lambdas. Lambdas are often used to create anonymous functions. This is not related to the fact that lambdas are implemented through anonymous classes. It is perfectly possible to create a named function, such as:

UnaryOperator<Integer> square = x -> x * x;

We may then apply this function as:

Integer x = square.apply(4);

If we want to create a recursive factorial function, we might want to write:

UnaryOperator<Long> factorial = x -> x == 0 
    ? 1 
    : x * factorial.apply(x - 1 );

But this won't compile because we can't use factorial while it is being defined. The compiler complains that “Cannot reference a field before it is defined”.

One possible solution is to first declare the field, and then initialize it later, in the constructor, or in an initializer:

UnaryOperator<Long> factorial;
{
  factorial = i -> i == 0 
      ? 1 
      : i * factorial.apply( i - 1 );
}

This works, but it is not very nice. There is however a much simpler way. Just add this. before the name of the function, as in:

UnaryOperator<Long> factorial = x -> x == 0 
    ? 1 
    : x * this.factorial.apply(x - 1 );

Not only this works, but it even allows making the reference final:

final UnaryOperator<Long> factorial = x -> x== 0 
    ? 1 
    : x * this.factorial.apply(x - 1 );

If you prefer a static field, just replace this with the name of the class:

static final UnaryOperator<Long> factorial = x -> x== 0 
    ? 1 
    : x * MyClass.factorial.apply(x - 1 );

Interesting things to note:

This function will silently produce an arithmetic overflow for factorial(26), producing a negative result.

It will produce 0 for factorial(66) and over, until around 3000, where is will overflow the stack since recursion is implemented on the stack. If you try to find the exact limit, you may be surprised to see that it sometimes happens and sometimes not, for the same values. Try the following example:

public class Test {

  static final UnaryOperator<Integer> count = x -> x  == 0
      ? 0
      : x + Test.count.apply(x - 1);

  public static void main(String[] args) {
    for (int i = 0;; i++) {
       System.out.println(i + ": " + count.apply(i));
    }
  }
}

Here's the kind of result you might get:

...
18668: 174256446
18669: 174275115
18670: 174293785
18671: 174312456
Exception in thread "main" java.lang.StackOverflowError

You could think that Java is able to handle 18671 level of recursion, but it is not. Try to call count(4000) and you will get a stack overflow. Obviously, Java is memoizing results on each loop execution, allowing to go much further than with a single call.

Of course, it is possible to push the limits much beyond by implementing recursion on the heap through the use of trampolining.

Another interesting point is that the same function implemented as a method uses much less stack space:

static int count(int x) {
  return x == 0
      ? 0
      : x + count(x - 1);
}

This method overflows the stack only around count(6200).

Java (programming language)

Opinions expressed by DZone contributors are their own.

Related

  • Reading an HTML File, Parsing It and Converting It to a PDF File With the Pdfbox Library
  • A Maven Story
  • JPA Criteria With Pagination
  • Ways To Reduce JVM Docker Image Size

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Core Program
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends: