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

Question

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!

Tim · Accepted Answer · 2009-08-14 17:58:12Z

3

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.

edited Aug 14, 2009 at 17:58

answered Aug 14, 2009 at 5:08

Tim

60.3k19 gold badges159 silver badges165 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Mamun Over a year ago

Thanks for this solution. Wrapper function seems best.

Mark Rushakoff · Accepted Answer · 2009-08-14 05:07:14Z

0

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]

answered Aug 14, 2009 at 5:07

Mark Rushakoff

260k47 gold badges412 silver badges401 bronze badges

Comments

outis · Accepted Answer · 2009-08-14 05:24:08Z

0

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.

edited Aug 14, 2009 at 5:24

answered Aug 14, 2009 at 5:12

outis

77.7k23 gold badges155 silver badges228 bronze badges

1 Comment

jason Over a year ago

Statics in functions aren't any better than globals, really.

Collectives™ on Stack Overflow

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

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related