How do I save the original argument in a recursive function in PHP?

Question

Hi, I'm in PHP working on an Euler problem. I have this function so far:

<?php
$biggest = 0;
$counter = 1;
function test($i){
    global $biggest;
    global $counter;
    if ($i == 1) {
     echo "I'm done! Took me $biggest steps";
    }
    else {
     if ($i%2 == 0) {
      $counter = $counter + 1;
      if ($counter>$biggest) {
       $biggest = $counter;
      }
      test($i/2); 
     }
     else {
      $counter = $counter + 1;
      if ($counter>$biggest) {
       $biggest = $counter;
      }
      test(3*$i+1);
     }
    }
} 

test(13);
?>

I have the problem mostly licked, but I can't seem to get back at the original input. The question is "When you have a number, if odd get 3n+1, when even, get n/2, do until returns 1. What starting value yields the most "steps" before you get to one?" I currently am returning the number of steps, but I keep resetting $i as I recurse, so I can't record what starting # yielded my $biggest number of steps.

How can I keep track of that number, but also not have it destroyed at the next instance of the loop? (I'll eventually wrap this in a for ($i=1, $i<1000000, $i++) loop)

Thanks!

Answer 1

It's easy, just pass it around as a parameter! Here's some python-ish pseudocode:

def func(start, arg):
    if foo(arg):
        return func(start, arg+1)
    else:
        return [start, arg]

Answer 2

A common approach is to pass the original argument through each time, so that when eventually you get to your base case, you still have it available. A primitive (and almost entirely unrelated example):

<?php

function fact($n) {
    if($n == 1) return 1;
    else return $n * fact($n - 1);
}

?>

This is an extremely basic implementation of the factorial function in PHP. Now say you wanted for whatever reason to have the initial value available in the final step: you'd build a wrapper function fact($n) that would call something like memory_fact($n, $initial):

<?php

function fact($n) {
    return memory_fact($n, $n);
}

function memory_fact($n, $initial) {
    if($n == 1) return 1;
    else return $n * memory_fact($n - 1, $initial);
}

?>

This way, memory_fact always knows where it started.

Answer 3

You don't need the globals; globals are evil. Try returning something useful from test(). Also, you'll find the test() above wastes many cycles. Try using memoization.

Here's a memoization example for calculating Fibonacci numbers:

function fib($n) {
    static $data = array(1, 1);
    if (!isset($data[$n])) {
        $data[$n] = fib($n-1) + fib($n-2);
    }
    return $data[$n];
}

Note that there are other time-efficent constant-space approaches to handle Fibonacci numbers (including one in O(log n) time), but the Collatz conjecture is a little trickier.