PHP 재귀 함수 예제

Lunar Dev·2024년 7월 10일
php

재귀함수 활용 예

💡 재귀함수란?
함수 안에 함수 본인을 다시 호출하는 것을 의미한다
이러한 재귀함수는 자신의 로직을 내부적으로 반복하다, 일정 조건이 만족되면
함수가 종료되고 반환 값이 있으면 반환 값을 반환한다

1. 재귀함수를 활용한 곱셈

  • 일반적인 곱셈
echo 5*10; // 출력 : 50
  • 함수를 활용한 곱셈
function multiply($a, $b) {
	return $a * $b;
}

echo multiply(5, 10); // 출력 : 50
  • 재귀함수를 활용한 곱셈
function recusiveMultiply($a, $b) {
	if($a == 0 || $b == 0) {
    	return 0;
    }
    
    return $a + recusiveMultiply($a, $b - 1);
}

2. 재귀함수를 활용한 팩토리얼

  • 재귀함수를 활용하지 않고 팩토리얼 구하기
function factorial($n) {
	$result = 1;
    for($i = 2; $i <= $n; $i++) {
        $result *= $i;
    }
    
	return $result;
}

echo factorial(5); // 출력 : 120
  • 재귀함수를 활용해서 팩토리얼 구하기
function recursiveFactorial($n) {
    if($n <= 1) {
        return 1;
    }

	return $n * recursiveFactorial($n - 1);
}

echo recursiveFactorial(5); // 출력 : 120

3. 재귀함수를 활용한 피보나치 수열

  • 재귀함수를 활용하지 않고 피보나치 수열 구하기
function fibonacci($n) {
    $a = 0;
    $b = 1;

    for($i = 0; $i < $n; $i++) {
        $temp = $a;
        $a = $b;
        $b = $temp + $b;
    }

    return $a;
}

echo fibonacci(10); // 출력 : 55

OR

function fibonacci($n) {
    if($n <= 1) {
        return $n;
    }

    $fib = array(0, 1);
    for($i = 2; $i <= $n; $i++) {
        $fib[$i] = $fib[$i - 1] + $fib[$i - 2];
    }

    return $fib[$n];
}

echo fibonacci(10); // 출력 : 55
  • 재귀함수를 활용해서 피보나치 수열 구하기
function recursiveFibonacci($n) {
    if($n <= 1) {
        return $n;
    } else {
        return recursiveFibonacci($n - 1) + recursiveFibonacci($n - 2);
    }
}

echo recursiveFibonacci(10); // 출력 : 55

4. 재귀함수를 활용한 하노이의 탑

  • 재귀함수를 활용하지 않은 하노이의 탑
function hanoi($n) {
    $moves = pow(2, $n) - 1;
    $stack = array();
    $stack[] = array('n' => $n, 'disk' => $n, 'from' => 'A', 'to' => 'C', 'aux' => 'B');

    while(!empty($stack)) {
        $task = array_pop($stack);
        $n = $task['n'];
        $disk = $task['disk'];
        $from = $task['from'];
        $to = $task['to'];
        $aux = $task['aux'];

        if($n == 1) {
            echo "$disk 번 원반을 $from 에서 $to 로 이동" . "<br>";
        } else {
            $stack[] = array('n' => $n - 1, 'disk' => $n - 1, 'from' => $aux, 'to' => $to, 'aux' => $from);
            $stack[] = array('n' => 1, 'disk' => $n, 'from' => $from, 'to' => $to, 'aux' => $aux);
            $stack[] = array('n' => $n - 1, 'disk' => $n - 1, 'from' => $from, 'to' => $aux, 'aux' => $to);
        }
    }

    return $moves;
}

echo "총 이동 횟수 : " . hanoi(3);

출력 : 
/*
    1 번 원반을 A 에서 C 로 이동
    2 번 원반을 A 에서 B 로 이동
    1 번 원반을 C 에서 B 로 이동
    3 번 원반을 A 에서 C 로 이동
    1 번 원반을 B 에서 A 로 이동
    2 번 원반을 B 에서 C 로 이동
    1 번 원반을 A 에서 C 로 이동
    총 이동 횟수 : 7
/*
  • 재귀함수를 활용한 하노이의 탑
function hanoi($n, $from, $to, $aux) {
    if($n == 1) {
        echo "1번 원반을 $from 에서 $to 로 이동" . "<br/>";
        return;
    }

    hanoi($n - 1, $from, $aux, $to);
    echo "$n 번 원반을 $from 에서 $to 로 이동" . "<br/>";
    hanoi($n - 1, $aux, $to, $from);
}

hanoi(3, 'A', 'C', 'B');

출력 : 
/*
    1 번 원반을 A 에서 C 로 이동
    2 번 원반을 A 에서 B 로 이동
    1 번 원반을 C 에서 B 로 이동
    3 번 원반을 A 에서 C 로 이동
    1 번 원반을 B 에서 A 로 이동
    2 번 원반을 B 에서 C 로 이동
    1 번 원반을 A 에서 C 로 이동
*/

5. 재귀함수를 활용한 병합 정렬(mergeSort)

  • 재귀함수를 활용하지 않은 병합 정렬
function mergeSort($array)
{
    $n = count($array);
    $size = 1;

    while ($size < $n) {
        for ($start = 0; $start < $n; $start += $size * 2) {
            $mid = $start + $size;
            $end = min($start + $size * 2, $n);
            merge($array, $start, $mid, $end);
        }
        $size *= 2;
    }

    return $array;
}

function merge(&$array, $start, $mid, $end)
{
    $left = array_slice($array, $start, $mid - $start);
    $right = array_slice($array, $mid, $end - $mid);

    $i = 0;
    $j = 0;
    $k = $start;

    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] <= $right[$j]) {
            $array[$k] = $left[$i];
            $i++;
        } else {
            $array[$k] = $right[$j];
            $j++;
        }

        $k++;
    }

    while ($i < count($left)) {
        $array[$k] = $left[$i];
        $i++;
        $k++;
    }

    while ($j < count($right)) {
        $array[$k] = $right[$j];
        $j++;
        $k++;
    }
}

$array = array(64, 34, 25, 12, 22, 11, 90);
$sortedArray = mergeSort($array);
echo '정렬 후 : ' . implode(",", $sortedArray); 
// 출력 : 정렬 후 : 11,12,22,25,34,64,90
  • 재귀함수를 활용한 병합정렬
function mergeSort($array)
{
    if(count($array) <= 1) {
        return $array;
    }

    $mid = floor(count($array) / 2);
    $left = array_slice($array, 0, $mid);
    $right = array_slice($array, $mid);

    $left = mergeSort($left);
    $right = mergeSort($right);

    return merge($left, $right);
}

function merge($left, $right)
{
    $result = array();
    $i = 0;
    $j = 0;

    while($i < count($left) && $j < count($right)) {
        if($left[$i] < $right[$j]) {
            $result[] = $left[$i];
            $i++;
        }else{
            $result[] = $right[$j];
            $j++;
        }
    }

    while($i < count($left)) {
        $result[] = $left[$i];
        $i++;
    }

    while($j < count($right)) {
        $result[] = $right[$j];
        $j++;
    }

    return $result;
}

$array = array(64, 34, 25, 12, 22, 11, 90);
$sortedArray = mergeSort($array);
echo '정렬 후 : ' . implode(",", $sortedArray); 
// 출력 : 정렬 후 : 11,12,22,25,34,64,90

6. 재귀함수를 활용한 빠른 정렬(quickSort)

  • 재귀함수를 활용하지 않은 빠른 정렬
function quickSort($array)
{
    $stack = array();
    array_push($stack, 0, count($array) - 1);

    while (!empty($stack)) {
        $end = array_pop($stack);
        $start = array_pop($stack);

        if ($start >= $end) continue;

        $pivot = $array[$end];

        $i = $start - 1;

        for ($j = $start; $j < $end; $j++) {
            if($array[$j] <= $pivot) {
                $i++;
                $temp = $array[$i];
                $array[$i] = $array[$j];
                $array[$j] = $temp;
            }
        }

        $i++;
        $temp = $array[$i];
        $array[$i] = $array[$end];
        $array[$end] = $temp;

        array_push($stack, $start, $i - 1);
        array_push($stack, $i + 1, $end);
    }

    return $array;
}

$array = array(64, 34, 25, 12, 22, 11, 90);
$sortedArray = quickSort($array);
echo '정렬 후 : ' . implode(",", $sortedArray);
  • 재귀함수를 활용한 빠른 정렬
function quickSort($array)
{
    if (count($array) <= 1) {
        return $array;
    }

    $pivot = $array[0];
    $left = array();
    $right = array();

    for ($i = 1; $i < count($array); $i++) {
        if ($array[$i] < $pivot) {
            $left[] = $array[$i];
        } else {
            $right[] = $array[$i];
        }
    }

    return array_merge(quickSort($left), array($pivot), quickSort($right));
}

$array = array(64, 34, 25, 12, 22, 11, 90);
$sortedArray = quickSort($array);
echo '정렬 후 : ' . implode(",", $sortedArray);

7. 재귀함수를 활용한 최대공약수(GCD) 계산

  • 재귀함수를 활용하지 않은 최대공약수 계산
function gcd($a, $b)
{
	while($b != 0) {
    	$temp = $b;
        $b = $a % $b;
        $a = $temp;
    }
    
    return $a; // 출력 : 5
}
  • 재귀함수를 활용한 최대공약수 계산
function recursiveGCD($a, $b)
{
	if($b == 0) return $a;
    return recursiveGCD($b, $a % $b);
}

8. 재귀함수를 활용한 거듭제곱 계산

  • 재귀함수를 활용하지 않은 거듭제곱 계산
function power($base, $exponent)
{
	$result = 1;
    while($exponent > 0) {
   		if($exponent % 2 == 1) {
        	$result *= $base;
        }
        
        $exponent = (int)($exponent / 2);
        $base *= $base;
    }
    
    return $result;
}

echo power(2, 3) . "<br>"; // 출력 : 2^3 = 8
  • 재귀함수를 활용한 거듭제곱 계산
function recursivePower($base, $exponent)
{
	if ($exponent == 0) return 1;
    if ($exponent % 2 == 0) {
    	$half = power($base, $exponent / 2);
        return $half * $half;
    }
    
    return $base * recursivePower($base, $exponent - 1);
}
echo recursivePower(2, 3) . "<br>"; // 출력 : 2^3 = 8

9. 재귀함수를 활용한 이진트리순회(중위 순회)

// 공통활용

class Node
{
    var $value = null;
    var $left = null;
    var $right = null;

    function __construct($value)
    {
        $this->value = $value;
    }
}

$root = new Node(1);
$root->left = new Node(2);
$root->right = new Node(3);
$root->left->left = new Node(4);
$root->left->right = new Node(5);
$root->right->left = new Node(6);
$root->right->right = new Node(7);
$root->left->left->left = new Node(8);
$root->left->left->right = new Node(9);
  • 재귀함수를 활용하지 않은 이진트리순회(중위)
function inorderTraversal($root)
{
    $stack = array();
    $current = $root;
    $result = array();

    while ($current != null || !empty($stack)) {
        while ($current != null) {
            array_push($stack, $current);
            $current = $current->left;
        }
        $current = array_pop($stack);
        $result[] = $current->value;
        $current = $current->right;
    }

    return $result;
}

$result = inorderTraversal($root);
echo implode(", ", $result); 
// 출력 : 8 4 9 2 5 1 6 3 7
  • 재귀함수를 활용한 이진트리순회(중위)
function recursiveInorderTraversal($root) {
	if($root == null) return;
	recursiveInorderTraversal($root->left);
    echo $node->value . " ";
    recursiveInorderTraversal($root->right);
}

// 출력 : 8 4 9 2 5 1 6 3 7
  • 순회 방식 소개
        1
       / \
      2   3
     / \ / \
    4  5 6  7
   / \
  8  9

// 왼쪽 하위 트리를 순회 후 루트노드를 방문한다
* 중위 순회 : 8 -> 4 -> 9 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7

// 루트노드 부터 왼쪽을 기준으로 따라 내려간다
전위 순회 : 1 -> 2 -> 4 -> 8 -> 9 -> 5 -> 3 -> 6 -> 7
// 가장 밑에서 부터 시작되고 루트노드를 마지막에 방문한다
후위 순회 : 8 -> 9 -> 4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1
// 루트노드 부터 레벨 별 왼쪽 오른쪽 순
층별 순회 : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

10. 재귀함수를 활용한 이진 검색

  • 재귀 함수를 활용하지 않은 이진 검색
function binarySearch($array, $x) 
{
	$left = 0;
    $right = count($array) - 1;
    
    while ($left <= $right) {
    	$mid = $left + (int)(($right - $left) / 2);
        if ($array[$mid] == $x) return $mid;
        
        if ($array[$mid] < $x) {
        	$left = $mid + 1;
        }else {
        	$right = $mid - 1;
        }
    }
    
    return -1;
}

$array = array(1, 3, 5, 7, 9, 11, 13, 15);
$x = 7;

$result = binarySearch($array, $x);

if ($result == -1) {
	echo '찾을 수 없습니다';
}else {
    echo "$result 번째 인덱스에 있습니다";
}

// 출력 : 3 번째 인덱스에 있습니다
  • 재귀 함수를 활용한 이진 검색
function recursiveBinarySearch($array, $left, $right, $x) 
{
	if($right >= $left) {
    	$mid = $left + floor(($right - $left) / 2);
        if ($array[$mid] == $x) return $mid;
        
        if ($array[$mid] > $x) {
        	return recursiveBinarySearch($array, $left, $mid - 1, $x);
        }
        
        return recursiveBinarySearch($array, $mid + 1, $right, $x);
    }
    
    return -1;
}

$array = array(1, 3, 5, 7, 9, 11, 13, 15);
$x = 7;

$result = recursiveBinarySearch($array, 0, count($array) - 1, $x);

if ($result == -1) {
	echo '찾을 수 없습니다';
}else {
    echo "$result 번째 인덱스에 있습니다";
}

// 출력 : 3 번째 인덱스에 있습니다

11. 재귀함수를 활용한 디렉토리 탐색

  • 재귀 함수를 활용하지 않은 디렉토리 탐색
function listFiles($dir) {
    $stack = [$dir];
    $files = [];

    while (!empty($stack)) {
        $currentDir = array_pop($stack);
        $entries = scandir($currentDir);

        foreach ($entries as $entry) {
            if ($entry != '.' && $entry != '..') {
                $path = $currentDir . '/' . $entry;
                if (is_dir($path)) {
                    array_push($stack, $path);
                } else {
                    $files[] = $path;
                }
            }
        }
    }

    return $files;
}
  • 재귀 함수를 활용한 디렉토리 탐색
function listFiles($dir) {
    $files = scandir($dir);
    foreach ($files as $file) {
        if ($file != '.' && $file != '..') {
            if (is_dir("$dir/$file")) {
                listFiles("$dir/$file");
            } else {
                echo "$dir/$file\n";
            }
        }
    }
}
profile
Lunar Dev
저장소
이전 포스트

PHP 문자열 - 2

다음 포스트

Database 데이터 모델링

0개의 댓글