Erlang递归函数 #

-module(recursion_review).
-export([factorial/1]).

factorial(0) -> 1;
factorial(N) when N > 0 -> N * factorial(N - 1).

-module(non_tail).
-export([sum/1, length/1]).

sum([]) -> 0;
sum([H | T]) -> H + sum(T).

length([]) -> 0;
length([_ | T]) -> 1 + length(T).

-module(tail_recursive).
-export([sum/1, length/1]).

sum(List) -> sum(List, 0).

sum([], Acc) -> Acc;
sum([H | T], Acc) -> sum(T, H + Acc).

length(List) -> length(List, 0).

length([], Acc) -> Acc;
length([_ | T], Acc) -> length(T, Acc + 1).

-module(tail_principle).
-export([count_down/1]).

count_down(N) -> count_down(N, []).

count_down(0, Acc) -> Acc;
count_down(N, Acc) when N > 0 -> count_down(N - 1, [N | Acc]).

-module(accumulator_basic).
-export([reverse/1, sum/1]).

reverse(List) -> reverse(List, []).

reverse([], Acc) -> Acc;
reverse([H | T], Acc) -> reverse(T, [H | Acc]).

sum(List) -> sum(List, 0).

sum([], Acc) -> Acc;
sum([H | T], Acc) -> sum(T, H + Acc).

-module(multi_accumulator).
-export([partition/2, split_at/2]).

partition(Pred, List) -> partition(Pred, List, [], []).

partition(_, [], TrueAcc, FalseAcc) -> 
    {lists:reverse(TrueAcc), lists:reverse(FalseAcc)};
partition(Pred, [H | T], TrueAcc, FalseAcc) ->
    case Pred(H) of
        true -> partition(Pred, T, [H | TrueAcc], FalseAcc);
        false -> partition(Pred, T, TrueAcc, [H | FalseAcc])
    end.

split_at(N, List) -> split_at(N, List, []).

split_at(0, List, Acc) -> {lists:reverse(Acc), List};
split_at(_, [], Acc) -> {lists:reverse(Acc), []};
split_at(N, [H | T], Acc) -> split_at(N - 1, T, [H | Acc]).

-module(complex_accumulator).
-export([group_by/2]).

group_by(KeyFun, List) -> 
    Result = group_by(KeyFun, List, #{}),
    maps:map(fun(_, V) -> lists:reverse(V) end, Result).

group_by(_, [], Acc) -> Acc;
group_by(KeyFun, [H | T], Acc) ->
    Key = KeyFun(H),
    Current = maps:get(Key, Acc, []),
    group_by(KeyFun, T, Acc#{Key => [H | Current]}).

-module(list_recursion).
-export([map/2, filter/2, foldl/3, foldr/3]).

map(_, []) -> [];
map(Fun, [H | T]) -> [Fun(H) | map(Fun, T)].

filter(_, []) -> [];
filter(Pred, [H | T]) ->
    case Pred(H) of
        true -> [H | filter(Pred, T)];
        false -> filter(Pred, T)
    end.

foldl(_, Acc, []) -> Acc;
foldl(Fun, Acc, [H | T]) -> foldl(Fun, Fun(H, Acc), T).

foldr(_, Acc, []) -> Acc;
foldr(Fun, Acc, [H | T]) -> Fun(H, foldr(Fun, Acc, T)).

-module(tree_recursion).
-export([sum/1, map/2, find/2]).

sum({node, Value, Left, Right}) ->
    Value + sum(Left) + sum(Right);
sum(empty) -> 0.

map(Fun, {node, Value, Left, Right}) ->
    {node, Fun(Value), map(Fun, Left), map(Fun, Right)};
map(_Fun, empty) -> empty.

find(Pred, {node, Value, Left, Right}) ->
    case Pred(Value) of
        true -> {found, Value};
        false ->
            case find(Pred, Left) of
                {found, _} = Result -> Result;
                not_found -> find(Pred, Right)
            end
    end;
find(_Pred, empty) -> not_found.

-module(nested_list).
-export([flatten/1, deep_map/2]).

flatten(List) -> flatten(List, []).

flatten([], Acc) -> Acc;
flatten([H | T], Acc) when is_list(H) ->
    flatten(T, flatten(H, Acc));
flatten([H | T], Acc) ->
    flatten(T, [H | Acc]).

deep_map(Fun, List) when is_list(List) ->
    [deep_map(Fun, Item) || Item <- List];
deep_map(Fun, Item) ->
    Fun(Item).

-module(linear_recursion).
-export([factorial/1, fibonacci/1]).

factorial(0) -> 1;
factorial(N) when N > 0 -> N * factorial(N - 1).

fibonacci(0) -> 0;
fibonacci(1) -> 1;
fibonacci(N) when N > 1 -> fibonacci(N - 1) + fibonacci(N - 2).

-module(tail_recursion).
-export([factorial/1, fibonacci/1]).

factorial(N) -> factorial(N, 1).

factorial(0, Acc) -> Acc;
factorial(N, Acc) when N > 0 -> factorial(N - 1, N * Acc).

fibonacci(N) -> fibonacci(N, 0, 1).

fibonacci(0, A, _B) -> A;
fibonacci(N, A, B) when N > 0 -> fibonacci(N - 1, B, A + B).

-module(mutual_recursion).
-export([is_even/1, is_odd/1]).

is_even(0) -> true;
is_even(N) when N > 0 -> is_odd(N - 1).

is_odd(0) -> false;
is_odd(N) when N > 0 -> is_even(N - 1).

-module(divide_conquer).
-export([merge_sort/1, quick_sort/1]).

merge_sort([]) -> [];
merge_sort([X]) -> [X];
merge_sort(List) ->
    {Left, Right} = split(List),
    merge(merge_sort(Left), merge_sort(Right)).

split(List) -> split(List, [], []).

split([], Left, Right) -> {Left, Right};
split([H | T], Left, Right) -> split(T, [H | Right], Left).

merge([], Right) -> Right;
merge(Left, []) -> Left;
merge([H1 | T1] = Left, [H2 | T2] = Right) ->
    if
        H1 =< H2 -> [H1 | merge(T1, Right)];
        true -> [H2 | merge(Left, T2)]
    end.

quick_sort([]) -> [];
quick_sort([Pivot | Rest]) ->
    {Smaller, Larger} = partition(Pivot, Rest),
    quick_sort(Smaller) ++ [Pivot] ++ quick_sort(Larger).

partition(Pivot, List) -> partition(Pivot, List, [], []).

partition(_, [], Smaller, Larger) -> {Smaller, Larger};
partition(Pivot, [H | T], Smaller, Larger) ->
    if
        H =< Pivot -> partition(Pivot, T, [H | Smaller], Larger);
        true -> partition(Pivot, T, Smaller, [H | Larger])
    end.

-module(state_recursion).
-export([process_list/2]).

process_list([], State) -> {done, State};
process_list([H | T], State) ->
    NewState = process_item(H, State),
    process_list(T, NewState).

process_item(Item, State) ->
    maps:update_with(count, fun(C) -> C + 1 end, 1, State).

-module(service_loop).
-export([start/0, loop/1]).

start() ->
    InitialState = #{count => 0},
    spawn(fun() -> loop(InitialState) end).

loop(State) ->
    receive
        {increment, N} ->
            NewState = maps:update_with(count, fun(C) -> C + N end, State),
            loop(NewState);
        {get_count, From} ->
            Count = maps:get(count, State, 0),
            From ! {count, Count},
            loop(State);
        stop ->
            ok
    end.

-module(stack_depth).
-export([bad/1, good/1]).

bad(0) -> done;
bad(N) -> bad(N - 1), ok.

good(0) -> done;
good(N) -> good(N - 1).

-module(memory_usage).
-export([bad_sum/1, good_sum/1]).

bad_sum([]) -> 0;
bad_sum([H | T]) -> H + bad_sum(T).

good_sum(List) -> good_sum(List, 0).

good_sum([], Acc) -> Acc;
good_sum([H | T], Acc) -> good_sum(T, H + Acc).

-module(optimization).
-export([process_large_list/1]).

process_large_list(List) ->
    process_large_list(List, [], 0).

process_large_list([], Acc, Count) ->
    {lists:reverse(Acc), Count};
process_large_list([H | T], Acc, Count) ->
    NewH = process_item(H),
    process_large_list(T, [NewH | Acc], Count + 1).

process_item(X) -> X * 2.

-module(parser).
-export([parse_tokens/1]).

parse_tokens(Tokens) -> parse_tokens(Tokens, []).

parse_tokens([], Acc) -> {ok, lists:reverse(Acc)};
parse_tokens([{error, _} = Error | _], _Acc) -> {error, Error};
parse_tokens([Token | Rest], Acc) ->
    Parsed = parse_token(Token),
    parse_tokens(Rest, [Parsed | Acc]).

parse_token({int, V}) -> {integer, V};
parse_token({str, V}) -> {string, V};
parse_token({atom, V}) -> {atom, V}.

-module(file_processor).
-export([process_lines/1]).

process_lines(Path) ->
    {ok, File} = file:open(Path, [read]),
    try
        process_lines(File, [])
    after
        file:close(File)
    end.

process_lines(File, Acc) ->
    case io:get_line(File, "") of
        eof -> {ok, lists:reverse(Acc)};
        {error, Reason} -> {error, Reason};
        Line ->
            Processed = process_line(Line),
            process_lines(File, [Processed | Acc])
    end.

process_line(Line) -> string:trim(Line).

-module(tree_walker).
-export([preorder/1, inorder/1, postorder/1]).

preorder({node, Value, Left, Right}) ->
    [Value | preorder(Left) ++ preorder(Right)];
preorder(empty) -> [].

inorder({node, Value, Left, Right}) ->
    inorder(Left) ++ [Value] ++ inorder(Right);
inorder(empty) -> [].

postorder({node, Value, Left, Right}) ->
    postorder(Left) ++ postorder(Right) ++ [Value];
postorder(empty) -> [].