Recursive fibonnaci never resolves for high numbers.

[ryanpcmcquen]

For numbers around 60 or higher, the recursive Fibonacci never returns. Or it just takes longer than I have patience for.

Example:

https://repl.it/@ryanpcmcquen/WoefulQuarrelsomePublishers-1

pub fn fibonacci_recursive(n: i32) -> u64 {
	if n < 0 {
		panic!("{} is negative!", n);
	}
	match n {
		0     => panic!("zero is not a right argument to fibonacci_recursive()!"),
		1 | 2 => 1,
		3     => 2,
		/*
		50    => 12586269025,
		*/
		_     => fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
	}
}

/**
 * Non recursive function.
 */
pub fn fibonacci(n: i32) -> u64 {
	if n < 0 {
		panic!("{} is negative!", n);
	} else if n == 0 {
		panic!("zero is not a right argument to fibonacci()!");
	} else if n == 1 {
		return 1;
	}

	let mut sum = 0;
	let mut last = 0;
	let mut curr = 1;
	for _i in 1..n {
		sum = last + curr;
		last = curr;
		curr = sum;
	}
	sum
}

fn main() {
    println!("{}", fibonacci(60));
    println!("{}", fibonacci_recursive(60));
}

[eliovir]

Of course it does not work. Such implementation gives exponential calls, so it is ineffective. I've just added some comments.

[Gkozd]

Hi Eliovir,
I tried and used as test subject and for learning purpose a part of your code.
Can you tell me maybe, why for 95-th number it start to panicking?:

"Enter a positive integer:
94

12200160415121876738

Enter a positive integer:
95
thread 'main' panicked at 'attempt to add with overflow', src/main.rs:22:19
note: run with RUST_BACKTRACE=1 environment variable to display a backtrace

all test code look like:

use std::io;

fn main() {

// most part of the "pub" code is from
// https://github.com/eliovir/rust-examples/blob/master/fibonacci.rs

pub fn fibonacci(n: usize) -> usize {

	if n == 0 {
		panic!("zero is not a right argument to fibonacci()!");
	} else if n == 1  {
		return 0;
	}
    else if n == 2 | 3 {
		return 1;
	}

	let mut sum = 0;
	let mut last = 0;
	let mut curr = 1;
	for _i in 3..n {
		sum = last + curr;
		last = curr;
		curr = sum;
	}
	sum
}

// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

println!("\n Fibonacci first twelve numbers:
0, 1, 1,   2, 3, 5,   8, 13, 21,  34, 55, 89...");

println!("\nInput n number of Fibonacci you want to be search!");

println!("\nType \"quit\" to end the program");
loop {
    let mut n = String::new();
    println!("\nEnter a positive integer:");

    io::stdin()
    .read_line(&mut n)
    .expect("Failed to read line");

    if n.trim() == "quit" {
        break;
    }

    let n: usize = match n.trim().parse() {
        Ok(num) => num,
        Err(err) => {
            println!("{}", err);

            break;
        }
    };

        println!("\n{}", fibonacci(n+1));
    }

}

[Gkozd]

Ok - changing to u128 will allow to "receive" n till 188 ->

"Enter a positive integer:
187

332825110087067562321196029789634457848

Enter a positive integer:
188
thread 'main' panicked at 'attempt to add with overflow', src/main.rs:20:19
note: run with RUST_BACKTRACE=1 environment variable to display a backtrace"