Hello everybody!

1) How can I find the maximum value in a single linked-list recursively?

this is what I tried to do:

``````int findMax(int key){
while (max != null){
if (max < max.getKey())
return(max.getNext());
}

}
``````

it ends up to an error.. :(

2) How can check palindrome in a single linked-list recursively?

Thank you for All ^ ^

The solution you have provided for the first question is not recursive. You can have a recursion that will stop when max.next() is null, and otherwise will return the max value between the current node and the next node.

``````int findMax(Node node)
{
if(node.next() == null)
{
return node.getKey();
}
else
{
return max(node.getKey(), findMax(node.next()));
}
}``````

And you will need a method that will call the recursion with head

``````int findMax()
{
{
return null;
}
else
{
}
}``````

Regarding the second question - how would you check for a palindrome in a non-recursive manner? Try to do this and maybe the recursion will seem more clear.

Good luck!

Thank you for quick helping, I'll try to run the code at home.
But I still don't understand how does the code work, where is the comparison exactly done! Thank you for explaining..

The comparison is done in this line:

``return max(node.getKey(), findMax(node.next()));``

Where you return the max of the current result and the result of the next recursion call. Try to visualize it... can you see it? :)

I understand that it is difficult to understand recursive when you learn about it the first time. (I did have difficulty understanding it as well when I first learned about it.) One way to be more clear about it is to follow its iteration and write it down in a paper. Write all variables you use in the function call before a call. Then, write them all again after the first call, and keep doing it until you hit the base case. Try to make the limit the call to at most 3 call before it hits the base case, so you would get an idea how it works.

``````// i.e.
// aList: 5 -> 10 -> 4 -> null
//
// findMax() 1st iteration
// current node is 5, next node is 10
// 10 (next node) is not null, comparing 5 with whatever comes back **
// findMax() 2nd iteration
// current node is 10, next node is 4
// 4 is not null, comparing 10 with whatever comes back **
// findMax() 3rd iteration
// current node is 4, next node is null
// next node is null, return 4

// now it is time to come back to each of the recursive call
// compare 4 with 10, 10 is max so return 10
// compare 5 with 10, 10 is max so return 10
// done``````

I agree with Taywin, recursions can be hard at the beginning. Let us try and review our code for a linked list of length 4, containing [22]->[43]->[107]->[45]->[null].
First, we call findMax(), it will call findMax(Node node) where node == head:

``````//Iteration 1

{
if(head.next() == null) //we know that head.next() != null, so we are going to the else clause.
{
return node.getKey();
}
else
{
return max(node.getKey(), findMax(node.next())); //meaning we need to return the max between 22 and the result of findMax(head.next()).
}
}``````

The method then needs to call to findMax(head.next()) in order to determine which one is bigger:

``````//Iteration 2

if(head.next() == null) //we know that node.next() != null, so we are going to the else clause.
{
return node.getKey();
}
else
{
return max(node.getKey(), findMax(node.next())); //meaning we need to return the max between 43 and the result of findMax(head.next()).
}
}``````

And again, the method needs to call to findMax(head.next().next()) in order to determine which one is bigger:

``````//Iteration 3

if(head.next() == null) //we know that node.next() != null, so we are going to the else clause.
{
return node.getKey();
}
else
{
return max(node.getKey(), findMax(node.next())); //meaning we need to return the max between 107 and the result of findMax(head.next()).
}
}``````

And yet again, the method has to call the findMax(head.next().next().next()) in order to determine which one is bigger, 107, the value of the current node checked, or the next node:

``````//Iteration 4

if(head.next() == null) //this node is the last one, and its next points to null (head.next().next().next().next() == null), therefore we are inside the if clause.
{
return node.getKey(); //simply return 45.
}
else
{
return max(node.getKey(), findMax(node.next())); //meaning we need to return the max between 45 and the result of findMax(head.next()).
}
}``````

Now, all the results are coming back to the calling methods. Iteration 4 returned the value of 45 to the calling method, which is the method shown in iteration 3. Meaning that iteration 3 now needs to compute:

``return max(107, 45)``

That means that iteration 3 returns 107 to the calling method, iteration 2. The method in iteration 2 will also need to compute and return its value:

``return max(43, 107)``

Meaning iteration 2 will return 107 to its calling method, iteration 1. Iteration 1 will also calculate and return:

``return max(22, 107)``

Meaning that the final result that will return to the user is 107, which is indeed the highest number stored in the linked list.

I hope that this step-by-step dive into the recursion helped you to understand the concept. Don't worry, even though it's hard to grasp at the beginning, it becomes easier as you practice it :)

Thaaaaaank you for your great help, I really appreciate your time and effort.
Now I see the code more clearer as tracing.. but still not creating a new algorithm ^^

I run the code in my program, but the keyword ( max ) in the last line was not
initialized!

I try to omit the ( max ) and edit the code like this:

``````int findMax(Node node){

if(node.getNext() == null)
{
return node.getKey();
}
else
{
int m = findMax(node.getNext());
if (node.getKey()> m)
return (node.getKey());
return m;

}
}
``````

but it always return the first element.. !

You can't omit the max, since this is the actual line that does the comparison between the two numbers - the number in the current node, and the number returned from the following nodes in the recursion. You can implement a max method of your own, or simply use the max(int a, int b) provided in the Math class.

I did the following max method:

``````int max (int a, int b){
Node node;
int maximam;
if (node.getKey() > node.getNext())
maximam = node.getKey();
return maximam;
}
``````

but there is an error :

operator > cannot be applied to int,Node

Sorry for annoying you all

Ok...
First, the method is accepting two integers, a and b - and then you trying to compare the nodes instead of a and b in question. The method should accept a and b and return the higher value of the two.

``````public int max(int a, int b)
{
if(a > b)
{
return a;
}
return b;
}``````

Can you see the difference between this and what you wrote?
Second, regarding the complication error - you are trying to compare an int (node.getKey()) and a node (node.getNext()).
Perhaps you want to compare it with node.getNext().getKey()

aha, so the comparison doesn't take parameters of the class type ( Node ), only int.
.....
Now the program compiles with no error, but it still returns only the first value ( key ),
I captured the code that I did to create a linked list, to find out the problem:

Is the way that I create the list right?

Please post the code as text and not as a picture...

``````import java.util.*;
import java.util.Scanner;

class Node{

int key;
Node next;

public Node (){

this.key=key;
next = null;
}

public    Node (int a){

key = a;
next = null;

}

public void setNext(Node n){
next = n;
}

public Node getNext(){
return next;
}

public int getKey(){
return key;
}

public void newNode(int n){
key = n;
Node i ;
else
{

while (i.getNext() != null)
i = i.getNext();
}
}

public int max(int a, int b){
if(a > b)
{
return a;
}
return b;
}

int findMax(Node node){

if(node.getNext() == null)
{
return node.getKey();
}
else
{
int m = findMax(node.getNext());

return max(node.getKey(), findMax(node.getNext()));
}
}

void findMax(){

System.out.println(" The maximum value is: " + findMax(head));

}

}

public class maxRecursion {

public static void main(String[] args) {

Node myList = new Node();
Scanner input=new Scanner(System.in);
System.out.println("Enter a set of integers, press y to continue and x to stop: ");
int n;
char exit = ' ';

do{
System.out.print("Enter an integer:  ");
n = input.nextInt();
myList.newNode(n);
System.out.print("continue?  ");
exit = input.next().charAt(0);

}while (exit != 'x' );
myList.findMax();

}
}``````

Your newNode(int n) method only inserts the new node if (head == null), but does nothing afterwards except to iterate all the way to the end.

``````public void newNode(int n)
{
key = n;
Node i ;
{
head = new Node(key); // Great, we will have a new node here.
}
else
{
while (i.getNext() != null)
{
i = i.getNext();
}
// ok, i is the last node here... now you need to insert the node.
}
}``````

Your list only has the first node inserted, which can explain your results...

``````public void newNode(int n)
{
key = n;
Node i ;
{
head = new Node(key); // Great, we will have a new node here.
}
else
{
while (i.getNext() != null)
{
i = i.getNext();
}

i.getNext()= new Node(key);
// ok, i is the last node here... now you need to insert the node.
}
}``````

Th insertion state is unexpected type,
I tried with:
i.getNext()= new Node(key);
i.getNext()= key;

How about the simple old fashioned

``i.next = new Node(key);``

:)

Yeeeeeh!,,
it's reeaally working... :)

This is my first try to create a linked list.. I need to get more trainings on that..
Thank you so much for all ^ ^

.......
for the second question ( palindrome ) I prefer to create another thread to be a whole complete reference for other..

Glad to hear that it's working! Try to work on the palindrome with the techniques you have learned :)