Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What causes this recursive function to crash compared to another nearly identical one? [duplicate]

Tags:

java

recursion

This causes a Stack Overflow error. I just need help explaining why this one crashes compared to the correct one which is similar. I have used the debugger, but it is still unclear to me.

public static void main(String[] args) {
    countForwards(5);
}
public static void countForwards( int num ) {
    if (num >= 0){
        countForwards(num--);
    }
    System.out.print(num + " ");
}

I know this is the solution but I don't understand why it is different

public static void countForwards( int num ) {
    if (num >= 0){
        countForwards(num - 1);
    }
    System.out.print(num + " ");
}
like image 460
JCCS Avatar asked Apr 23 '15 05:04

JCCS


People also ask

How can a recursive algorithm cause a system to crash?

The need to use a stack to store return values means that recursive techniques can be heavy on the memory use. A stack is only so big and a stack overflow would cause the program to crash. Non-recursive solutions are therefore likely to be more efficient when it comes to processing time and storage.

What causes stack overflow in recursion?

The most-common cause of stack overflow is excessively deep or infinite recursion, in which a function calls itself so many times that the space needed to store the variables and information associated with each call is more than can fit on the stack. An example of infinite recursion in C.

What happens when the recursion calling is applied on two functions?

Either way the result will be the same, in this particular case it doesn't matter: both recursive calls will be computed and added together before being returned, from the calling place you'll only see the end result of the sum. Show activity on this post. It doesn't matter which function is called first.

Which helps to break from recursion?

A better approach would be to eliminate the recursion and use a Stack collection holding a class representing what would have been recursive state, iterate in a loop and just return true when you want.


1 Answers

countForwards(num--) passes the original value of num to the recursive call, which means the recursion never ends.

countForwards(--num) would allow the recursion to end.

After seeing all the traffic this question got, I thought it would be worth it to expand the answer a little.

As paxdiablo commented, even though countForwards(--num) allows the recursion to terminate, it behaves differently than countForwards(num-1).

Both variants would cause the following series of recursive calls :

countForwards(5)
countForwards(4)
countForwards(3)
countForwards(2)
countForwards(1)
countForwards(0)
countForwards(-1)

but they will output a different series of numbers when the recursion unwinds :

num - 1 -- num
-1 -1
0 -1
1 0
2 1
3 2
4 3
5 4

The reason for the difference is that num-1 doesn't change the value of num while --num decrements num.

like image 100
Eran Avatar answered Sep 22 '22 15:09

Eran